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>

【版權聲明】轉載請注明出處：