56. Merge Intervals.md

56. Merge Intervals

思路

题目要求合并区间。

思路一

先将区间数组按照start大小进行排序，然后再从前往后遍历找到重叠的区间合并即可。详细过程见代码注释。
需要注意的是:
sort中的比较函数compare要声明为静态成员函数或全局函数，不能作为普通成员函数，否则会报错: invalid use of non-static member function。 原因是非静态成员函数是依赖于具体对象的，而std::sort这类函数是全局的，因此无法在sort中调用非静态成员函数。 静态成员函数或者全局函数是不依赖于具体对象的,可以独立访问，无须创建任何对象实例就可以访问。同时静态成员函数不可以调用类的非静态成员。例:

static bool mycmp(const int &a, const int &b) 
    {
        return a > b;  // 这样的话直接调用sort(vc.begin(), vc.end(), mycmp)就是从大到小排序了
    }

或者用lambda函数直接传入sort:

sort(vc.begin(), vc.end(), [](const int &a, const int &b){return a > b;});

时间复杂度O(nlogn)，空间(不算返回结果)复杂度O(1)。

思路二

不进行排序，而是用一个map记录每一个区间end到start的隐射，注意map中key是自动排好序的。这样就可以使用low_bound函数快速进行查找。 从前往后遍历一遍区间数组并不断加入到map隐射中，遇到重叠的合并即可。
注意:

• 根据此处，map中的erase(it)函数在在C++11中, 返回的是被删除的后面一个位置的迭代器。
• lower_bound(first, last, val): 返回有序数组或容器的[first, last)范围内第一个大于或等于val的元素的位置(指针或者迭代器,下同);
• upper_bound(first, last, val): 返回有序数组或容器的[first, last)范围内第一个大于val的元素的位置;
• 类似sort函数，上面两个函数都可以传入一个comp来自定义元素大小关系。

由于map的实现是红黑树，所以查找删除插入都为O(logn)，所以总体复杂度也为O(nlogn),时间复杂度O(n)

C++

思路一

class Solution {
private:
    static bool mycmp(const Interval &a, const Interval &b){
        return a.start < b.start;
    }
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        vector<Interval>res;
        int n = intervals.size();
        if(!n) return res;
        sort(intervals.begin(), intervals.end(), mycmp);
        int cur_start = intervals[0].start, cur_end = intervals[0].end;
        for(int i = 1; i < n; i++){
            if(intervals[i].start > cur_end){ // 没有重叠的，应该把当前start和end加入到结果数组中并更新start
                res.push_back(Interval(cur_start, cur_end));
                cur_start = intervals[i].start;
                //cur_end = intervals[i].end;
            }
            //else{
            cur_end = max(cur_end, intervals[i].end); // 更新end
            //}
        }
        res.push_back(Interval(cur_start, cur_end)); // 不要忘了把最后一个push进res
        return res;
    }
};

思路二

class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        map<int, int> r2l; // 不能用unordered_map，因为lower_bound需要有序
        for (auto i: intervals) {
            int s = i.start, e = i.end;
            auto it = r2l.lower_bound(i.start);
            while (it != r2l.end() && it->second <= i.end) {
                s = min(s, it->second);
                e = max(e, it->first);

                auto it_bk = it;
                it++;
                r2l.erase(it_bk);
                //it = r2l.erase(it); // 在C++11中, erase返回的是被删除的后面一个位置, 所以上面三行相当于这一行
                // it现在指向的是原来的位置的下一个位置
            }
            r2l[e] = s;
        }
        vector<Interval> ans;
        for (auto &p: r2l) 
            ans.push_back(Interval(p.second, p.first));
        return ans;
    }
};