Leetcode 57 Insert Interval

扯闲篇

为啥写这个题目？因为这个题目是merge interval的一个小变种。知道了merge怎么做 然后想一想这个怎么做 就会做了。

题目

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Given intervals[1,3],[6,9], insert and merge[2,5]in as[1,5],[6,9].

Example 2:

Given[1,2],[3,5],[6,7],[8,10],[12,16], insert and merge[4,9]in as[1,2],[3,10],[12,16].

This is because the new interval[4,9]overlaps with[3,5],[6,7],[8,10].

分析

题目说的很清楚了，首先数组上来默认是排序的，然后告诉我们了，不加入新的数组 数组之间本来是没有重合的。

啥意思啊？

1. 不用排序

2. 数组本来不需要归并，加入了一个新数组才需要归并

然后呢？

所以我们之前如果做过归并 那就知道了，这道题目的点在两个

1. 找到开始归并的点

2. 归并

好了 归并的话就按照归并那道题目的要求来做呗。那要如何找到归并点呢？归并点就是interval[i].end > newInterval.start的第一个点。

那merge的结束点呢？  结束点就是interval[i].start >newInterval.end 的第一个点。  这就可以做了

代码自己点开看哈~~~~