题解 | #合并区间#

/**
 * 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;
        ans.push_back(intervals[0]);
        // stack<Interval> stk;
        // stk.push(intervals[0]);
        int i = 1;
        while(i<n)
        {
            // Interval a = stk.top();

            Interval b = intervals[i];
            if(ans.back().end >= b.start) // back() 就是末尾
            {
                // 合并
                // stk.pop();
                // stk.push(Interval(a.start, max(a.end, b.end)));
                ans.back().end =  max(ans.back().end, b.end);
            }
            else
            {
                // stk.push(b);
                ans.push_back(b);
            }

            i++;
        }

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

        //     stk.pop();
        // }

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

        return ans;


    }
};

官解做法 和我思路一样 只是不用栈