扯閑篇
為啥寫這個(gè)題目？因?yàn)檫@個(gè)題目是merge interval的一個(gè)小變種。知道了merge怎么做 然后想一想這個(gè)怎么做 就會(huì)做了。
題目
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].
分析
題目說的很清楚了，首先數(shù)組上來默認(rèn)是排序的，然后告訴我們了，不加入新的數(shù)組 數(shù)組之間本來是沒有重合的。
啥意思?。?/p>
1. 不用排序
2. 數(shù)組本來不需要?dú)w并，加入了一個(gè)新數(shù)組才需要?dú)w并
然后呢？
所以我們之前如果做過歸并 那就知道了，這道題目的點(diǎn)在兩個(gè)
1. 找到開始?xì)w并的點(diǎn)
2. 歸并
好了 歸并的話就按照歸并那道題目的要求來做唄。那要如何找到歸并點(diǎn)呢？歸并點(diǎn)就是interval[i].end > newInterval.start的第一個(gè)點(diǎn)。
那merge的結(jié)束點(diǎn)呢？ ?結(jié)束點(diǎn)就是interval[i].start >newInterval.end 的第一個(gè)點(diǎn)。 ?這就可以做了
