Leetcode 57 - Insert Interval（区间问题）

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

题意

给一些互不重合并且已经排好序的区间，现在加入一个新的区间b，要求将b合并进去。

思路

算法1

其实和区间合并那道题差不多，但是需要判断的是我们的新区间b需要加入的位置。

当新区间b.start <= a[i].start的时候，需要将b加入进去。

有一些细节需要注意一下。但是感觉稍微有点难写呐= =

首先，判断第一个插入的是a[0]还是b：如果是a[0]，之后的循环就从1开始；否则从0开始。

对于之后的循环：

如果b.start <= a[i].start并且b还没有被插入：我们插入b。否则，插入a。

算法2

对于我们新加入的区间b，和原来集合里面的每一个区间i，只有这三种情况：

于是，我们分别分析一下这3种情况：

b.start > a.end：我们只需要加入a，然后i++。退出循环的条件：a全部加入。b.end < a.start：之后的a由题目知道是不重合的，并且从这个位置开始已经不重合了，那么我们直接结束循环。a, b覆盖：我们将a和b合成一个新的区间b，然后继续循环。

从上面可以知道，我们结束循环的条件为：1或者2。

从1退出的话，说明a全部加入，我们只需要加入b。从2退出的话，说明b及之后的a都应加入。

并且，因为只能从1或者2退出循环，说明我们的区间不存在覆盖问题，因此在加入b和之后的a的过程中，只需要做的是push_back，而不需要进行合并。

代码

algorithm 1

class Solution { public: vector<Interval> insert(vector<Interval>& a, Interval b) { vector<Interval> ans; int n = a.size(); if (n) { int i = 1; bool flag = false; if (b.start <= a[0].start) { ans.push_back(b); i = 0; flag = true; } else { ans.push_back(a[0]); } for (; i < n; i++) { if (!flag && b.start <= a[i].start) { if (b.start <= ans.back().end) ans.back().end = max(ans.back().end, b.end); else ans.push_back(b); flag = true; i--; } else { if (a[i].start <= ans.back().end) ans.back().end = max(ans.back().end, a[i].end); else ans.push_back(a[i]); } } if (!flag) { if (b.start <= ans.back().end) ans.back().end = max(ans.back().end, b.end); else ans.push_back(b); } } else { ans.push_back(b); } return ans; } };

algorithm 2

class Solution { public: vector<Interval> insert(vector<Interval>& a, Interval b) { vector<Interval> ans; auto it = a.begin(); for (it; it != a.end(); it++) { if (b.start > (*it).end) ans.push_back(*it); else if (b.end < (*it).start) break; else { b.start = min(b.start, (*it).start); b.end = max(b.end, (*it).end); } } //add b ans.push_back(b); //add remaining a for (it; it != a.end(); it++) ans.push_back(*it); return ans; } };