Interval - Summary

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

第一，排序。在一般情况下，按照interval的start升序排序，在必要情况下，对于start相同的interval，按照interval的end的降序排序。

第二，greedy。有时候是两个interval之间的greedy，有时候是一群interval之间的greedy。

第三，map。c++里的map，是用红黑树实现的，这里为了方便就叫map。当前两板斧都无法奏效的时候，可以试试这个。

然而排序常常和greedy一起使用。先排序，再greedy，是对付interval最常见的解法。当然这种套路远不仅限于interval类的题目。一个简单的题目是Leetcode 56. Merge Intervals.

Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

在排序之后，我们遍历数组，当两个interval有overlap的时候，我们取最小的start和最大的end。因为排序的结果，最小的start一定更早出现，所以我们只需要贪婪地去取最大的end就可以了。来看一下代码。

vector<Interval> merge(vector<Interval>& ins) {
        if (ins.empty()) return vector<Interval>{};
        sort(ins.begin(), ins.end(), [](const Interval & a, const Interval & b) -> bool{ return a.start < b.start; });
        vector<Interval> res {ins[0]};
        for (int i = 1; i < ins.size(); ++i) {
            if (res.back().end < ins[i].start) res.push_back(ins[i]);
            else    res.back().end = max(res.back().end, ins[i].end);
        }
        return res;
    }




再来看一个同样是sort+greedy的题目。Leetcode 57. Insert Interval.

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times.

因为题目已经sort好了，所以我们只需要做greedy的部分就可以。先找到需要开始插入的地方，也就是找到第一个end在newInterval的start之后的interval。简单来说，插入的地方，newInterval的start需要在两个interval的end之间。找到了开始插入的地方，我们向后遍历。当有overlap的时候，我们贪婪地取newInterval和遍历经过的interval两者之间更小的start和更大的end。这就是newInterval merge之后的结果。最后我们再把不必要的interval给删掉。来看一下代码。

vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        int i=0;
        while(i<intervals.size() && intervals.at(i).end<newInterval.start) ++i;
        int m = i;
        while(i<intervals.size() && intervals.at(i).start<=newInterval.end){
            newInterval = Interval(min(intervals[i].start, newInterval.start), max(intervals[i].end, newInterval.end));
            ++i;
        }
        if(m < i)  intervals.erase(intervals.begin()+m, intervals.begin()+i);
        intervals.insert(intervals.begin()+m,newInterval);
        return intervals;
    }

再来一道类似的题目。Leetcode 435. Non-overlapping Intervals. 题目要求：

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

其实我本人在最早接触greedy算法的时候，学习的就是这个例子，可谓是非常经典。简单的逻辑就是，当有两个interval相互重叠的时候，我们一定要删去一个。那么删去哪一个呢？答案是删去end比较大的那个。这个可以用prove by contradiction轻松证明。来看一下借鉴自官方solution的code，其中pre记录的是目前为止保留的上一个interval。我这里把solution里面的compare function用lamda塞进去了。

int eraseOverlapIntervals(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const Interval& i1, const Interval& i2)->bool{return i1.start < i2.start;});
        int res = 0, pre = 0;
        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i].start < intervals[pre].end) {
                res++;
                if (intervals[i].end < intervals[pre].end) pre = i;
            }
            else pre = i;
        }
        return res;
    }

我们目前为止所看到的greedy，都是两个interval之间的互相比较。那么有没有一群interval之间的比较，取greedy呢？有的。来看一道来自一亩三分地中的Facebook面经。

给定一堆interval（如果我们管这个list叫IntervalList）， 和一个target interval 我们的目标是去merge这些interval，让merge的结果能够『cover』这个target interval， 求这种merge所需的原interval的最少个数是多少

来看楼里的一个python solution。

def find_min_intervals(intervals, target): 
 intervals.sort() 
 res = 0 
 cur_target = target[0] 
 i = 0 
 max_step = 0 
 while i < len(intervals) and cur_target < target[1]: 
  while i < len(intervals) and intervals[i][0] <= cur_target: 
   max_step = max(max_step, intervals[i][1]) 
   i += 1 
  cur_target = max_step 
  res += 1 
 return res if cur_target >= target[1] else 0

这里有两点说明。第一，其实并不需要全部排序，只需要找出和target有overlap的interval进行排序。第二，关于greedy。在inner while loop里面，我们所需要找的，就是满足start比cur_target要小的interval中，end最大的那个。这样去最大的end可以让加入的这个interval，最有价值，延展到最远。一开始的cur_target是target的start，后面的cur_target就是上一个加入的interval的end(为了保持区间不中断)。

使用好sort和greedy，已经能解决大部分的interval的题目。然而，有些interval的题目，并不很典型，但是可以借助map来解决。map干的事情一般来说就是自动排序，方便查找。使用map来解决的interval问题，并没有太多的共同点。这里只是简单分享一下。

第一个简单粗暴的例子就是Leetcode 436. Find Right Interval.题目废话太多，简单来说就是对于每一个interval，返回第一个在它右边的interval。对于一个interval在自己右边的定义，就是它的start大于等于自己的end。

看一下官方的solution:

vector<int> findRightInterval(vector<Interval>& intervals) {
        map<int, int> hash;
        vector<int> res;
        int n = intervals.size();
        for (int i = 0; i < n; ++i)    hash[intervals[i].start] = i;
        for (auto in : intervals) {
            auto itr = hash.lower_bound(in.end);
            if (itr == hash.end()) res.push_back(-1);
            else res.push_back(itr->second);
        }
        return res;
    }

借助map自带的排序和lower_bound功能，这道题非常容易就解决了。

第二个简单粗暴的例子，Leetcode 253. Meeting Room II.

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required. For example, Given [[0, 30],[5, 10],[15, 20]], return 2.

其实就是寻找最多有多少个interval同时重叠。想象一下自己按照时间的发展来记录这些会议的出现，每有一个会议开始，就加一，每有一个会议结束，就减一。我们只要用map来记录这些会议的开始与结束就可以了。

int minMeetingRooms(vector<Interval>& intervals) {  
    map<int, int> mp;  
    for(auto x: intervals) {
        mp[x.start]++;
        mp[x.end]--;  
    }
    int res = 0, sum = 0;  
    for(auto x: mp) {
     sum += x.second;
        res = max(res, sum);  
    }
    return res;  
} 

最后一个例子是Leetcode 352. Data Stream as Disjoint Intervals. 描述和代码略复杂，就不复制了。在一个官方solution中提到两种方法，一种用vector维护出现的interval，线性时间插入新的interval，常数时间返回；另一种是用map维护出现的interval，O(lgn)时间插入新的interval，线性时间返回结果。具体情况具体分析咯。

总结一下，一般来说interval的题目无外乎insert, merge, overlap, contained等等。sort可以使这些interval达成某种性质，基于这种性质我们可以用greedy来寻找答案。当这个方法失灵的时候，可以考虑是否可以map是否会有帮助。

https://www.quora.com/What-is-the-problem-if-we-sort-the-intervals-according-to-their-finishing-time-like-the-interval-scheduling-problem-Why-is-it-necessary-to-sort-according-to-the-starting-time-in-the-interval-partitioning-problem

But I think what you mean is, why can't we sort on finishing time and then process the intervals from first to last, like in interval scheduling? And I think the reason is, for interval partitioning you need to keep track of which processes are currently running, or else you don't know which resources are free. So you need to know when they start to be able to account for that.

But for interval scheduling you actually don't need to know which processes are currently running. When a process finishes you can easily check whether the resource would have been available or not, and if it was, then clearly it should have processed that interval, so we can count it.