区间问题总结

Interval类型题

Interval类型的题目很烧脑，这里尽量总结一下，要多复习。

https://zhuanlan.zhihu.com/p/26657786

这种题的思路是：1.由于本身start和end都是无序的，所以第一步是先要针对start或者end进行排序，具体针对start还是end需要具体问题具体分析，一般来说针对start进行排序的情况比较多；2.对于已经排好序的数组使用greedy

https://www.1point3acres.com/bbs/thread-432526-1-1.html
我的体验是， 如果能改成类似经典问题的话 [寻找最多non overlapping interval]类型的题目，就是按end排序。 按end排序只> 需要考虑一个情况就是[3,5],[7,8],[1,10]这样。 如果这个是个反例，那得考虑start排序。

1. 646 + 435 + 452
2. 253 + 253
3. 56 + 57

By end 排序：

这种题的鼻祖问题是schedule problem，也就是leetcode 646. Maximum Length of Pair Chain。
646.Maximum Length of Pair Chain，schedule：schedule问题的思想就是为了能有更多的interval，我们更关心的是interval结束的时间，越早结束代表着我们有更多interval的可能性更大，所以我们将intervals按照结束时间sort。
排序结束后，我们就要分析使用greedy进行分析：对于结束时间最早的元素，我们肯定要加到结果的count中；对于结束时间第二早的元素，如果他的开始时间大于第一个元素的结束时间，那么我们也加入结果count并且目前最后结束的时间是第二个元素的结束时间，如果不大于那么我们最后结束时间还是第一个元素的结束时间。依次类推，我们知道需要maintain一个endTime。

class Solution {
    public int findLongestChain(int[][] pairs) {
        if(pairs.length==0)
            return 0;
        Arrays.sort(pairs, (a, b) -> {
            return a[1] - b[1];
        });
        int count = 1;
        int end = pairs[0][1];
        for(int i =1;i<=pairs.length-1;i++){
            if(pairs[i][0]>end){
                count++;
                end = pairs[i][1];
            }
        }
        return count;
    }
}

435.Non-overlapping Intervals: 这道题与schedule problem可以说一模一样，只是改变了问的方式，所以我们可以先求最大可能不overlap的个数，然后size减去这个数就是结果了。

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length==0)
            return 0;
        Arrays.sort(intervals, (a, b)->{
            return a[1]-b[1];
        });
        
        int count = 1;
        int minEnd = intervals[0][1];
        for(int i =1;i<=intervals.length-1;i++){
            if(intervals[i][0]>=minEnd){
                count++;
                minEnd = intervals[i][1];
                
            }
        }
        
        return intervals.length-count;
    }
}

452.Minimum Number of Arrows to Burst Balloons:

class Solution {
    public int findMinArrowShots(int[][] points) {
        if(points.length==0)
            return 0;
        Arrays.sort(points, (a, b)->{
            return a[1]-b[1];
        });
        
        int count = 1;
        int minEnd = points[0][1];
        for(int i =1;i<=points.length-1;i++){
            if(points[i][0]>minEnd){
                count++;
                minEnd = points[i][1];
            }
        }
        
        return count;
    }
}

---

By start 排序

252.Meeting Rooms：想象一下只有一个房间，肯定是先开始的人先用，后来的人看看房间有没有人，有人说明被占了，没人则可以使用。所以这道题我们按照start time进行排序，然后看有没有重叠既可。

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b)->{
            return a[0] - b[0];
        });
        for(int i =1;i<=intervals.length-1;i++){
            if(intervals[i][0]<intervals[i-1][1]){
                return false;
            }
        }
        
        return true;
    }
}

253.Meeting Rooms II: 这道题和252一样，都是先对start进行排序，因为先来的人肯定先用教室。不同的是这道题可以有多个教室，问题是需要的最少的教室数量。考虑到我们可以有多个教室，并且这些教室的endTime是不同的，所以我们需要maintain一个Priority Queue去记录目前使用的教室的结束时间去最快找到最小的结束时间。

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b)->{
            return a[0] - b[0];
        });
        
        PriorityQueue<Integer> endTime = new PriorityQueue<>();
        for(int[] interval:intervals){
            if(endTime.size()==0){
                endTime.offer(interval[1]);
            }
            else {
                int minEndTime = endTime.poll();
                if(interval[0]>=minEndTime){
                    endTime.offer(interval[1]);
                }
                else {
                    endTime.offer(minEndTime);
                    endTime.offer(interval[1]);
                }
            }
        }
        return endTime.size();
    }
}

56.Merge Intervals: 这个题不算可以直接应用scheduling problem的方法。如果你按end排序， 那么最容易举的反例就是 [3,5],[6,7],[1,10]。显然这三个应该归并到一起， 但是因为按照end排序， 这三个反而不会相交。
题目是希望找到可以merge起来的所有interval，那某种程度上来说是想找相交的interval的最小起始点和最大终止点。所以这里的做法是按start排序， 然后更新end， 把所有与之相交的interval合并成一个大interval。

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length==0)
            return intervals;
        Arrays.sort(intervals, (a, b) -> {
            return a[0] - b[0];
        });

        List<int[]> ans = new LinkedList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];
        for(int i =1;i<=intervals.length-1;i++){
            if(intervals[i][0]<=end){
                end = Math.max(end, intervals[i][1]);
            }
            else {
                ans.add(new int[]{start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        
        ans.add(new int[]{start, end});
        
        int[][] res = new int[ans.size()][2];
        for(int i =0;i<=ans.size()-1;i++){
            res[i] = ans.get(i);
        }
        return res;
    }
}

57.Insert Interval：与56题的思路一样，我们比较newInterval的start和排好序的Interval的end，如果start大于end，说明一定不存在overlap，直接将Interval放入结果中；如果start<=end，代表可能存在overlap，但这道题与56的区别在于这时我们只是知道NewInterval的start小于Interval的end，并不一定存在overlap

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> ans = new LinkedList<>();
        for(int[] interval:intervals){
            if(newInterval==null||newInterval[0]>interval[1]){
                ans.add(interval);
            }
            else {
                if(newInterval[1]<interval[0]){//如果newInterval的end小于interval的start，那么这种情况是没有overlap的
                    ans.add(newInterval);
                    ans.add(interval);
                    newInterval=null;
                }
                else {//其他情况一定有overlap，画图可以看出来
                    newInterval[0] = Math.min(newInterval[0], interval[0]);
                    newInterval[1] = Math.max(newInterval[1], interval[1]);
                }
            }
        }
        if(newInterval!=null){
            ans.add(newInterval);
        }
        
        int[][] res = new int[ans.size()][2];
        for(int i =0;i<=ans.size()-1;i++){
            res[i] = ans.get(i);
        }
        
        return res;
    }
}

729. My Calendar I : 这道题可以brute force去做，但是每次book都需要和所有元素进行比较。
     一个很好的提升思路是可以从56题中得到思路,使用一个LinkedList存储元素并且按照start进行排序。这时想要没有overlap，条件是插入的新元素的start大于(第一个start小于它的元素的end)，并且新元素的end小于(第一个start大于它的元素的start)。比如我们已经有[(2, 5), (8, 10), (14, 16)]，我们想要插入(9, 13)，我们需要找到9前面的start也就是8，比较8的end与9是否overlap，在找到9后面的start也就是14，比较14与10是否overlap。
     由此进一步提升，我们可以使用一个binary search tree，tree的每个node都是一个HashMap，key是start，value是end。所以我们可以使用java的TreeMap，这样book的时间复杂度是O(logn)。

如何用一个式子表示两个interval没有overlap：Math.max(start1, start2)>Math.min(end1, end2)

/*
729. My Calendar I
Medium

446

29

Favorite

Share
Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
Example 1:

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.
 

Note:

The number of calls to MyCalendar.book per test case will be at most 1000.
In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].
*/

class MyCalendar {
    TreeMap<Integer, Integer> calendar;
    public MyCalendar() {
        calendar = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        Integer prev = calendar.floorKey(start);
        Integer next = calendar.ceilingKey(start);
        if(prev!=null && calendar.get(prev)>start){
            return false;
        }
        if(next!=null && next<end){
            return false;
        }
        calendar.put(start ,end);
        return true;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */

731. My Calendar II: 相当于求overlap的overlap。如何用一个式子表示两个interval没有overlap：Math.max(start1, start2)>Math.min(end1, end2)

/*
731. My Calendar II
Medium

444

67

Favorite

Share
Implement a MyCalendarTwo class to store your events. A new event can be added if adding the event will not cause a triple booking.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A triple booking happens when three events have some non-empty intersection (ie., there is some time that is common to all 3 events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
Example 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.
 

Note:

The number of calls to MyCalendar.book per test case will be at most 1000.
In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].
*/
class MyCalendarTwo {
    List<int[]> calendar;
    List<int[]> overlap;

    public MyCalendarTwo() {
        calendar = new LinkedList<>();
        overlap = new LinkedList<>();       
    }
    
    public boolean book(int start, int end) {
        for(int[] c:calendar){
            if(Math.max(c[0], start)<Math.min(c[1], end)){          
                int overlapStart = Math.max(c[0], start);
                int overlapEnd = Math.min(c[1], end);
                for(int[] o:overlap){
                    if(Math.max(o[0], overlapStart)<Math.min(o[1], overlapEnd )){           
                        overlap.clear();
                        return false;
                    }
                }
                overlap.add(new int[]{overlapStart, overlapEnd});
            }
        }
        calendar.add(new int[]{start, end});
        return true;
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(start,end);
 */