解决方法56. 合并区间 - 力扣LeetCode按照区间的左边界排序假如有区间已经按照左边界排好序[ij] [kg]如果[ij] [kg], 如果k大于j则[ij]和[kg]一定不再一个区间。如果[ij] [kg], 如果k小于j则[ij]和[kg]一定在一个区间。区间末尾取j和g的最大值。合并后的区间为[imax(j,g)]class Solution { public: vectorvectorint merge(vectorvectorint intervals) { vectorvectorint result; if(intervals.size() 0) { return result; } // 按照区间的左边做从小到大排序 auto cmp [](const vectorint a, const vectorint 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) { // 如果[ij] [kg], 如果k大于j则[ij]和[kg]一定不再一个区间。 if(intervals[i][0] result.back()[1]) { result.push_back(intervals[i]); } else { // 如果[ij] [kg], 如果k小于j则[ij]和[kg]一定在一个区间。区间末尾取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; } }; vectorInterval merge(vectorInterval intervals) { // write your code here int len intervals.size(); if (len 1) { return intervals; } vectorNode 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_mapint, int table; int sum 0; vectorInterval 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应该排在前面这样可以保证合并为一个区间
)
