题解 | #合并区间#

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
  public:
    // 排序
    static bool comp(const Interval& a, const Interval& b) {
        return a.start < b.start; // 增序排序
    }
    // 之前笔试时遇到过相似的题
    // 先用 O(Nlogn) 时间来做下 空间O(N)
    vector<Interval> merge(vector<Interval>& intervals) {

        int n = intervals.size();
        if (n < 2) {
            return intervals;
        }

        // 排序
        sort(intervals.begin(), intervals.end(), comp);
        vector<Interval> ans;
        stack<Interval> stk;
        stk.push(intervals[0]);
        int i = 1;
        while(i<n)
        {
            Interval a = stk.top();

            Interval b = intervals[i];
            if(a.end >= b.start)
            {
                // 合并
                stk.pop();
                stk.push(Interval(a.start, max(a.end, b.end)));
            }
            else
            {
                stk.push(b);
            }

            i++;
        }

        // 从栈中取出
        while(!stk.empty())
        {
            ans.push_back(stk.top());

            stk.pop();
        }

        sort(ans.begin(), ans.end(), comp);

        return ans;


    }
};

自己扣的做法

用了栈 想到了 之前做过的括号消除 空间O（n）

时间 因为用了sort 平均是O(nlogn) 恩满足题目的要求了