LeetCode:Merge Intervals

given a collection of intervals, merge all overlapping intervals.

for example,

given <code>[1,3],[2,6],[8,10],[15,18]</code>,

return

<code>[1,6],[8,10],[15,18]</code>.

对若干个区间进行合并，使合并后的区间没有重叠

先对区间按照左边界排序，然后顺序扫描，合并重叠的区间即可。             

代码1在原区间数组上操作，不使用额外的空间，但是需要删除多余的区间，这样会移动数组元素

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

<code>/**</code>

<code> </code><code>* definition for an interval.</code>

<code> </code><code>* struct interval {</code>

<code> </code><code>*     int start;</code>

<code> </code><code>*     int end;</code>

<code> </code><code>*     interval() : start(0), end(0) {}</code>

<code> </code><code>*     interval(int s, int e) : start(s), end(e) {}</code>

<code> </code><code>* };</code>

<code> </code><code>*/</code>

<code>class</code>

<code>solution {</code>

<code>private</code><code>:</code>

<code>    </code><code>static</code>

<code>bool</code> <code>comp(interval a, interval b)</code>

<code>    </code><code>{</code>

<code>        </code><code>return</code>

<code>a.start &lt; b.start;</code>

<code>    </code><code>}</code>

<code>public</code><code>:</code>

<code>    </code><code>vector&lt;interval&gt; merge(vector&lt;interval&gt; &amp;intervals) {</code>

<code>        </code><code>if</code><code>(intervals.empty())</code><code>return</code>

<code>intervals;</code>

<code>        </code><code>sort(intervals.begin(), intervals.end(), comp);</code>

<code>        </code><code>vector&lt;interval&gt;::iterator it1 = intervals.begin(), it2 = it1 + 1;</code>

<code>        </code><code>while</code><code>(it1 != intervals.end() &amp;&amp; it2 != intervals.end())</code>

<code>        </code><code>{</code>

<code>            </code><code>if</code><code>(it2-&gt;start &lt;= it1-&gt;end)</code>

<code>            </code><code>{</code>

<code>                </code><code>if</code><code>(it1-&gt;end &lt; it2-&gt;end)it1-&gt;end = it2-&gt;end;</code>

<code>                </code><code>it2++;</code>

<code>            </code><code>}</code>

<code>            </code><code>else</code>

<code>                </code><code>//[it1+1, it2)范围内的区间可以从原数组删除</code>

<code>                </code><code>it1 = intervals.erase(it1+1, it2);</code>

<code>                </code><code>it2 = it1 + 1;</code>

<code>        </code><code>}</code>

<code>        </code><code>if</code><code>(it1 != intervals.end())</code>

<code>            </code><code>intervals.erase(it1 + 1, it2);</code>

<code>};</code>

代码2用新数组来存储合并后的区间

<code>        </code><code>vector&lt;interval&gt; res;</code>

<code>        </code><code>res.push_back(intervals[0]);</code>

<code>        </code><code>for</code><code>(</code><code>int</code>

<code>i = 1; i &lt; intervals.size(); i++)</code>

<code>            </code><code>interval &amp;p = res.back();</code>

<code>            </code><code>if</code><code>(intervals[i].start &gt; p.end)res.push_back(intervals[i]);</code>

<code>if</code><code>(intervals[i].end &gt; p.end)p.end = intervals[i].end;</code>

<code>res;</code>

【版权声明】转载请注明出处：