酒店价格

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int[] arr = new int[100000];
        int max = 0;
        while(input.hasNext()){
            int a=input.nextInt();
            int b=input.nextInt();
            if(b>max)
                max=b;
            int c=input.nextInt();
            for(int i=a;i<=b;i++){
                arr[i]=c;
            }
        }
        int index=0;
        while(index<=max){
            if(arr[index]==0)
                index++;
            else{
                int begin = index;
                int value = arr[index];
                while(value==arr[index])
                    index++;
                if(index!=max+1)
                    System.out.print("["+begin+", "+(index-1)+", "+value+"],");
                else
                    System.out.print("["+begin+", "+(index-1)+", "+value+"]");
            }
        }
    }
}

	

/**

• 题目描述
  酒店房间的价格录入是通过时间段来录入的，比如10月1日至10月7日800元，10月8日至10月20日500元，
  请实现以下函数int[][] merge(int[][] dateRangePrices)，输入是某个酒店多个日期段的价格，
  每个日期段（终止日期大于等于起始日期）和对应的价格使用长度为3的数组来表示，
  比如[0, 19, 300], [10, 40, 250]分别表示从某天开始第1天到第20天价格都是300，
  第11天到第41天价格都是250，这些日期端有可能重复，重复的日期的价格以后面的为准， 请以以下规则合并并输出合并结果：
  1.相邻两天的价格如果相同，那么这两个日期段应该合并
  2.合并的结果应该以起始日期从小到大排序
  输入描述:
  输入数据包括多行，如样例输入所示。
  输出描述:
  输出数据为一行，如样例输出所示
  */
  package pastexampaper2017;
  import java.awt.List;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Iterator;
  import java.util.Scanner;
  class Room implements Comparable{
  private int begin=0;
  private int end=0;
  private int price=0;
  Room(int begin,int end,int price){

   this.begin=begin;
   this.end=end;
   this.price=price;
  

  }
  public int getBegin() {

   return begin;
  

  }
  public void setBegin(int begin) {

   this.begin = begin;
  

  }
  public int getEnd() {

   return end;
  

  }
  public void setEnd(int end) {

   this.end = end;
  

  }
  public int getPrice() {

   return price;
  

  }
  public void setPrice(int price) {

   this.price = price;
  

  }
  public int compareTo(Object room) {

   int diff=this.getPrice()-((Room) room).getPrice();
   if(diff==0) {
       int diff0=this.getEnd()-(((Room) room).getBegin()-1);
       if(diff0==0) {
           return 1;
       }
   }
   return 0;
  

  }
  public String toString() {

    return "[" + this.getBegin() + ", " + this.getEnd()+ ", " + this.getPrice() + "]";
  

  }
  public static Room merge(Room room1,Room room2) {

    if(room1.compareTo(room2)==1) {
        room1.setBegin(room1.getBegin());
        room1.setEnd(room2.getEnd());
        room1.setPrice(room1.getPrice());
        room2.setBegin(0);
        room2.setEnd(0);
        room2.setPrice(0); 
    }else {
        return null;
    }
    return room1;
  

  }
  }
  public class Main12 {
  public static void main(String[] args) {

       Scanner sc=new Scanner(System.in);
       ArrayList list=new ArrayList();
       while (sc.hasNext()){
           int begin = sc.nextInt();
           int end = sc.nextInt();
           int price = sc.nextInt();
           list.add(new Room(begin,end,price));
       }
       //System.out.println(list);
       Object[] obj = list.toArray();
      for(int i=0;i<obj.length;i++){
           for(int j=i;j<obj.length;j++) {
               Room room1 = (Room) obj[i];
               Room room2 = (Room) obj[j];
               Room.merge(room1, room2);
           }
       }
      for(int i=0;i<obj.length-1;i++) {
           if(obj[i].toString().equals("[0, 0, 0]")) {
               continue;
           }else {
               System.out.print(obj[i]+",");
           }
      }
      if(obj[obj.length-1].toString().equals("[0, 0, 0]")) {
       return;
   }else {
       System.out.print(obj[obj.length-1]);
   }            
  

  }
  }
  测试用例通过10%，但是我觉得没问题，不知道大家觉得是不是有错误呢

//区间树，见算法导论第14章
//用数组暴力模拟的前提是起始日期和终止日期都不会很大
//算是偷鸡的做法
//直接借用了TreeMap，其中key代表日期的起点，value存放一个数据结构（start，end，value）
//我们在向map中插入之前先查询map，把所有本次中覆盖的集合删除掉（有可能会有不完全覆盖的现象，需要处理）
//之后合并连续日期并且价格相同的情况
//以下第一行是添加的输入比如(3, 10, 100)
//第二行是集合中原有的数据比如(1,4,10),(5,6,101),(7,8,19),(9,10,100)
//比如添加 ----------------------------------
//   --------    ----------   ---------   ------
//      ^            ^            ^         ^
//    需要截断       直接删掉     直接删掉     截断
//变成
//  ---|----------------------------------|---
//再判断挨着的是否需要合并
//牛客的数据集是真的菜，模拟居然能过。。。
//另外注意TreeMap的SubMap不是一个真的map，对SubMap的修改会影响TreeMap本身
//以上 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static class Node implements Comparable<Node>{
        int low, high, val;
        public Node(int low, int high, int val) {
            this.low = low;
            this.high = high;
            this.val = val;
        } @Override public int compareTo(Node o) {
            return this.val - o.val;
        }
    }

    public static void insert(TreeMap<Integer, Node> map, Node node) {
        NavigableMap<Integer, Node> subMap = map.subMap(node.low, true, node.high, true);
        while (subMap.size() > 0) {
            Node tmp = subMap.pollFirstEntry().getValue();
            if (subMap.size() == 0 && tmp.low <= node.high && node.high < tmp.high) {
                map.put(node.high + 1, new Node(node.high + 1, tmp.high, tmp.val));
            }
        }
        //check last
        Map.Entry<Integer, Node> entry = map.floorEntry(node.low);
        if (entry != null) {
            Node last = entry.getValue();
            if (last.high > node.high) {
                map.put(node.high + 1, new Node(node.high + 1, last.high, last.val));
            }
            if (last.high >= node.low) {
                last.high = node.low - 1;
            }
            if (last.high == node.low - 1 && last.val == node.val) {
                map.remove(last.low);
                node.low = last.low;
            }
        }
        //check next
        entry = map.ceilingEntry(node.high);
        if (entry != null && entry.getValue().low == node.high + 1 && entry.getValue().val == node.val) {
            map.remove(entry.getValue().low);
            node.high = entry.getValue().high;
        }
        map.put(node.low, node);
    }


    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        TreeMap<Integer, Node> map = new TreeMap<>();
        String line;
        while ((line = br.readLine()) != null) {
            int[] tmp = lineToIntArray(line);
            insert(map, new Node(tmp[0], tmp[1], tmp[2]));
        }
        StringBuffer sb = new StringBuffer();
        int i = 0;
        for (Map.Entry<Integer, Node> entry: map.entrySet()) {
            Node tmp = entry.getValue();
            sb.append("[");
            sb.append(tmp.low);
            sb.append(", ");
            sb.append(tmp.high);
            sb.append(", ");
            sb.append(tmp.val);
            sb.append("]");
            if (++i != map.size())
                sb.append(",");
        }
        System.out.println(sb);
    }

    public static int[] lineToIntArray(String line) {
        String[] arr = line.trim().split(" ");
        int[] ans = new int[arr.length];
        for (int i = 0; i < arr.length; i++)
            ans[i] = Integer.parseInt(arr[i]);
        return ans;
    }
}

用一个table[i][j]数组表示i到j的价格，根据题意往数组里面填价格，最后搜索table里面有价格的元素，组合一下输出。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] table = new int[100000];
        int start = 0, end, price = 0;
        int i, j;
        int max = 0;
        while (sc.hasNext()) {
            start = sc.nextInt();
            end = sc.nextInt();
            price = sc.nextInt();
            for (i = start; i <= end; i++) {
                table[i] = price;
            }
            if (end > max)
                max = end;
        }

        boolean first=true;
        for (i = 0; i <= max; i++) {
            if (table[i] != 0) {
                start = i;
                while (i+1 <= max && table[i] == table[i + 1])
                    i++;
                if(first) {
                    System.out.printf("[%d, %d, %d]", start, i, table[i]);
                    first = false;
                } else System.out.printf(",[%d, %d, %d]", start, i, table[i]);
            }
        }
    }
}