[LeetCode] Overlapping/Non-Overlapping Intervals

LeetCode裡面關于Overlapping/Non-Overlapping的主要有一下幾類：

- 尋找重疊/非重疊區間（具體區間數組）結果

- 計算重疊/非重疊區間個數

- 合并重疊區間，并傳回合并後的區間數組

相關題目為：

- 56. Merge Intervals

- 57. Insert Interval

- 252. Meeting Rooms

- 253. Meeting Rooms II

- 435. Non-overlapping Intervals

- 452. Minimum Number of Arrows to Burst Balloons

基本有兩類模闆，一類直接Interval類sort，一類分别sort區間的起、止點。排好序後，僅需判斷後一個的start在前一個區間之内即可判斷是否存在overlapping。因為兩個區間的包含關系主要隻有四種情況：

// 對任意區間[A,B], [C,D]
A      B               A      B            A     B            A              B 
     C     D      C      D             C           D            C      D
           

以56. Merge Intervals為例給出這兩類解題模闆：

vector<Interval> merge(vector<Interval>& intervals) {
    if (!intervals.size())   return intervals;
    sort(intervals.begin(), intervals.end(), [](Interval& a, Interval& b) {return a.start < b.start;});
    vector<Interval> res{intervals[]};
    for (int i = ; i < intervals.size(); i++) {
        if (res.back().end >= intervals[i].start)
            res.back().end = max(res.back().end, intervals[i].end);
        else
            res.push_back(intervals[i]);
        }
        return res
}
           

vector<Interval> merge(vector<Interval>& intervals) {
    if (!intervals.size())   return intervals;
        vector<Interval> res;
        vector<int> starts, ends;
        for (auto a : intervals) {
            starts.push_back(a.start);
            ends.push_back(a.end);
        }
        sort(starts.begin(),starts.end());
        sort(ends.begin(),ends.end());
        for (int i = , j = ; i < starts.size(); i++) {
            if (i == starts.size() -  || starts[i+] > ends[i]) {
                res.push_back(Interval(starts[j], ends[i]));
                j = i + ;
            }
         }
        return res;
}