最长递增子序列

Leetcode-729 :my-calendar-i

Leetcode-731 :my-calendar-ii

Leetcode-732 :my-calendar-iii

Calendar-I：

问题描述：

实现一个日历功能，book函数需要返回日程安排是否有冲突。区间为前闭后开。

>MyCalendar();
>MyCalendar.book(10, 20); // returns true
>MyCalendar.book(15, 25); // returns false
>MyCalendar.book(20, 30); // returns true
>Explanation: 
>The first event can be booked.  The second can't because time 15 is already booked by another event.
>The third event can be booked, as the first event takes every time less than 20, but not including 20.

>//使用两个List保存区间的开始和结束时间点，每次添加一个事件，遍历已有List，查看是否有冲突，
>//时间复杂度 O(n)
>class MyCalendar {
   private final List<Integer> starts;
   private final List<Integer> ends;
   public MyCalendar() {
       starts = new ArrayList<>();
       ends = new ArrayList<>();
   }
   
   public boolean book(int start, int end) {
       for(int i = 0;i<starts.size();i++){
           if(start >= ends.get(i) || end <= starts.get(i)){
               continue;
           }else{
               return false;
           }
       }
       starts.add(start);
       ends.add(end);
       return true;
   }
>}
>//解法二，使用TreeMap保存已有的时间节点，利用二叉搜索树的性质来找到插入节点左右两边的节点，快速判断
>//时间复杂度: O(logN)
>public class MyCalendar {
   private TreeMap<Integer, Integer> map;
   public MyCalendar() {
       map = new TreeMap<>();
   }
   public boolean book(int start, int end) {
       Integer last = map.floorKey(start);
       Integer next = map.ceilingKey(start);
       if (last != null && next == null && start < map.get(last)) {
           return false;
       }
       if (last == null && next != null && end > next) {
           return false;
       }
       if (last != null && next != null && (start < map.get(last) || end > next)) {
           return false;
       }
       map.put(start, end);
       return true;
   }
>}

Calendar-II：

问题描述：

实现一个类似问题1中的日历功能，要求最多只能有一个冲突事件。

>MyCalendar();
>MyCalendar.book(10, 20); // returns true
>MyCalendar.book(50, 60); // returns true
>MyCalendar.book(10, 40); // returns true
>MyCalendar.book(5, 15);  // returns false
>MyCalendar.book(5, 10);  // returns true
>MyCalendar.book(25, 55); // returns true
>Explanation: 
>The first two events can be booked.  The third event can be double booked.
>The fourth event (5, 15) can't be booked, because it would result in a triple booking.
>The fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked.
>The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked with the third event;
>the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

>//	此问题的关键即如何检测冲突区间的个数，当插入一个区间的时候，有两种情况
>//  1. 此区间会导致整个事件中冲突个数 > 1,拒绝插入返回false
>//  2. 此区间会导致整个事件中没有冲突或者冲突为1.插入并返回true
>// 可以使用一种巧妙的区间计数办法来检测冲突。我们可以维护一个时间线的数组time[]，对于一个区间[s,e）来说
>// 使得 time[s]+1, time[e]-1,然后遍历一遍数组就可以很快扽到冲突个数啦，举个例子：
>// 有三个区间 [1,2) [2,3) [3,4)来说我们将数组从前往后也就是按时间的先后顺序遍历
>// time[1] = 1,time[2] = -1, 然后区间[2,3)来了，time[2] = -1 + 1 = 0,time[3] = -1,
>//  依次计数，最后得到time[1] = 1,time[2] = time[3] = 0, time[4] = -1,遍历整个数组并将每一个值相
>//  并记录最大值，可以得到最大值为1
>//  说明是没有冲突的。 因为第一个区间的2最为结束时间赋值为-1，第二个区间的2最为开始时间应该+1，正好消
>//  了。也就是没有冲突
>//  那么如果[1,2) [1,3) [1,4)，来说呢，time[1] = 3, time[2] = -1,time[3] = -1, time[4] = -1;
>//  首先按照时间顺序一次遍历 time[1]为3，也就是说 这个时间点开始的区间有3个的时候还没有任何一个区间结  //  束，说明这三个区间是冲突的。
>class MyCalendarTwo {
   
   TreeMap<Integer,Integer> map;
   
   public MyCalendarTwo() {
       map = new TreeMap<>();
   }
   
   public boolean book(int start, int end) {
       map.put(start,map.getOrDefault(start,0)+1);
       map.put(end,map.getOrDefault(end,0)-1);
       
       int cnt = 0;
       for(int c : map.values()){
           cnt += c;
           if(cnt > 2){//检测到冲突超过1个之后，取消插入然后返回false
               map.put(start,map.getOrDefault(start,0)-1);
               map.put(end,map.getOrDefault(end,0)+1);
               return false;
           }
       }
       return true;
   }
>}

Calendar-III：

问题描述：

设计一个日历，可以添加任何区间的时间，不管其有没有冲突，要求返回最大冲突的区间个数

>MyCalendarThree();
>MyCalendarThree.book(10, 20); // returns 1
>MyCalendarThree.book(50, 60); // returns 1
>MyCalendarThree.book(10, 40); // returns 2
>MyCalendarThree.book(5, 15); // returns 3
>MyCalendarThree.book(5, 10); // returns 3
>MyCalendarThree.book(25, 55); // returns 3
>Explanation: 
>The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.
>The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking.
>The remaining events cause the maximum K-booking to be only a 3-booking.
>Note that the last event locally causes a 2-booking, but the answer is still 3 because
>eg. [10, 20), [10, 40), and [5, 15) are still triple booked.

>// 采用类似日历II中的区间冲突检测方法，直接返回最大的区间冲突次数即可。
>class MyCalendarThree {
   private final Map<Integer,Integer> map;
   public MyCalendarThree() {
       map = new TreeMap<>();
   }
   
   public int book(int start, int end) {
       map.put(start,map.getOrDefault(start,0)+1);
       map.put(end,map.getOrDefault(end,0)-1);
       int cnt = 0;
       int max = Integer.MIN_VALUE;
       for(int c :map.values()){
           cnt += c;
           max = Math.max(max,cnt);
       }
       return max;
   }
>}