Leetcode 56 - Merge Intervals（区间合并）

2019-11-08 02:18:53

字体：大中小

来源：转载

供稿：网友

github仓库：https://github.com/lzed/leetcode

题意

给定若干个区间，合并这些区间。

思路

算法1

先将区间排序，然后每次选定一个区间i，遍历之后的区间j，找到最后一个能够合并的区间后，合并。然后区间的起点的i跳转到j + 1。

算法2

假如我们现在结果ans里面已经有一些区间了，最后一个区间为x（x.end一定是ans里面最大的）。

对于下一个区间y，如果y.start <= x.end，说明能够和x重合，我们将x.end更新为max(x.end, y.end)。

如果不满足能够重合，说明是一个新的区间，然后放到结果里面去就好。

代码

algorithm 1

bool cmp(Interval& a, Interval& b) { return a.start == b.start ? a.end < b.end : a.start < b.start;}class Solution {public: vector<Interval> merge(vector<Interval>& a) { sort(a.begin(), a.end(), cmp); vector<Interval> ans; int n = a.size(); for (int i = 0; i < n;) { int ed = a[i].end, j = i + 1; for (; j < n; j++) { if (a[j].start <= ed) ed = max(ed, a[j].end); else {j--; break;} } ans.push_back(Interval(a[i].start, ed)); i = j + 1; } return ans; }};

algorithm 2

bool cmp(Interval& a, Interval& b) { return a.start == b.start ? a.end < b.end : a.start < b.start;}class Solution {public: vector<Interval> merge(vector<Interval>& a) { sort(a.begin(), a.end(), cmp); vector<Interval> ans; int n = a.size(); if (n) { ans.push_back(a[0]); for (int i = 1; i < n; i++) { if (a[i].start <= ans.back().end) ans.back().end = max(ans.back().end, a[i].end); else ans.push_back(a[i]); } } return ans; }};

上一篇：OpenFace源码阅读（一）——Readme索引

下一篇：面试题６－－利用前序和中序遍历重构二叉树－－递归方法