56. 合并区间(思维)

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        stack<pair<int, int>> s;
        int len = intervals.size();
        if(len == 0) return ans;
        typedef pair<int, int> p;
        vector<pair<int, int>> v;
        for (int i = 0; i < len; i++) {
            v.push_back(p(intervals[i][0], intervals[i][1]));
        }
        sort(v.begin(), v.end(), [](const pair<int, int> a, const pair<int, int> b) {
            if (a.first == b.first) return a.second < b.second;
            return a.first < b.first;
            });
        s.push(p(v[0].first, v[0].second));
        for (int i = 1; i < len; i++) {
            if (s.top().second >= v[i].first) {
                pair<int, int> tmp = p(min(s.top().first,v[i].first), max(v[i].second, s.top().second));
                s.pop();
                s.push(tmp);
            }
            else {
                pair<int, int> tmp = p(v[i].first, v[i].second);
                s.push(tmp);
            }
        }
        while(s.size() != 0) {
            vector<int> x{ s.top().first, s.top().second };
            ans.push_back(x);
            s.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};