解决方法：
56. 合并区间 - 力扣（LeetCode）
按照区间的左边界排序
假如有区间已经按照左边界排好序，[i，j] [k，g]
如果[i，j] [k，g], 如果k大于j，则[i，j]和[k，g]一定不再一个区间。
如果[i，j] [k，g], 如果k小于j，则[i，j]和[k，g]一定在一个区间。区间末尾取j和g的最大值。合并后的区间为[i，max(j,g)]
class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { vector<vector<int>> result; if(intervals.size() == 0) { return result; } // 按照区间的左边做从小到大排序 auto cmp = [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; }; sort(intervals.begin(), intervals.end(), cmp); result.push_back(intervals[0]); for(int i = 1; i < intervals.size(); ++i) { // 如果[i，j] [k，g], 如果k大于j，则[i，j]和[k，g]一定不再一个区间。 if(intervals[i][0] > result.back()[1]) { result.push_back(intervals[i]); } else { // 如果[i，j] [k，g], 如果k小于j，则[i，j]和[k，g]一定在一个区间。区间末尾取j和g的最大值 result.back()[1] = max(result.back()[1], intervals[i][1]); } } return result; } };/** * Definition of Interval: * class Interval { * public: * int start, end; * Interval(int start, int end) { * this->start = start; * this->end = end; * } * } */ class Solution { public: /** * @param intervals: interval list. * @return: A new interval list. */ struct Node { int val; int flag; Node(int v, int f) { val = v; flag = f; } }; vector<Interval> merge(vector<Interval> &intervals) { // write your code here int len = intervals.size(); if (len <= 1) { return intervals; } vector<Node> nodes; for (auto& e : intervals) { nodes.push_back(Node(e.start, -1)); nodes.push_back(Node(e.end, 1)); } sort(nodes.begin(), nodes.end(), [](Node& a, Node& b) { if (a.val < b.val) { return true; } else if (a.val == b.val && a.flag < b.flag) { return true; } return false; }); unordered_map<int, int> table; int sum = 0; vector<Interval> result; int start = 0; for (auto& n : nodes) { if (sum == 0) { start = n.val; } sum += n.flag; if (sum == 0) { Interval interval(start, n.val); result.push_back(interval); } } return result; } };扫描线：累加和为0表示，已经构成一个完整的区间。如果a区间的last和b区间的first相同，则b区间的first应该排在前面，这样可以保证合并为一个区间