Problem:
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]
.
Idea:
Sweep line
Solution:
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Runtime: 12 ms class Solution { public: vector<Interval> merge(vector<Interval>& intervals) { if (intervals.empty()) return {}; std::sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b){ return a.start < b.start; }); vector<Interval> ans; for (const auto& interval : intervals) { if (ans.empty() || interval.start > ans.back().end) { ans.push_back(interval); } else { ans.back().end = max(ans.back().end, interval.end); } } return ans; } }; |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 |
""" Author: Huahua Runtime: 69 ms """ class Solution(object): def merge(self, intervals): ans = [] for interval in sorted(intervals, key=lambda x: x.start): if not ans or interval.start > ans[-1].end: ans.append(interval) else: ans[-1].end = max(ans[-1].end, interval.end) return ans |
Related Problems:
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment