【LeetCode】56. Merge Intervals

题目描述

Given a collection of intervals, merge all overlapping intervals.

For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

解题思路

先对区间根据第一个元素进行排序。 然后每次判断下一个区间是否和当前区间有交集，若有，则扩展区间。否则，说明当前区间终止，结束当前区间并开始一个新的区间。 注意，此题使用的是闭区间。

AC代码

/** * 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 compareFn(const Interval& i1, const Interval& i2) { return (i1.start < i2.start || (i1.start == i2.start && i1.end < i2.end)); } vector<Interval> merge(vector<Interval>& intervals) { vector<Interval> ans; if (intervals.empty()) return ans; sort(intervals.begin(), intervals.end(), compareFn); for (int idx = 0; idx < intervals.size(); ++idx) { int start = intervals[idx].start; int end = intervals[idx].end; int nextIdx = idx + 1; for (; nextIdx < intervals.size(); ++nextIdx) { //overlap, expand if (intervals[nextIdx].start <= end) { end = max(end, intervals[nextIdx].end); } //no overlap, push back current interval else { Interval v(start, end); ans.push_back(v); break; } } // reach the last interval if (nextIdx >= intervals.size()) { Interval v(start, end); ans.push_back(v); } idx = nextIdx - 1; } return ans; } };