InterviewBit – Merge Overlapping Intervals

Source: Merge Overlapping Intervals

Given a collection of intervals, merge all overlapping intervals.

For example:

Given [1,3],[2,6],[8,10],[15,18],

return [1,6],[8,10],[15,18].

Make sure the returned intervals are sorted.

---

解題：

1. 是否重疊（可執行合併）須視intervals[i]的左端是否被涵蓋於intervals[i-1]的區間之內，故在題目未說明資料是否經過排序的情況下應先將所有區間數列依左端大小進行升冪排列；
2. 當發現有被納入區間的左端，便執行intervals[i]的右端確認：也在intervals[i-1]的區間之內＝＞更新右端值；大於intervals[i-1]的右端＝>不調整。而因為此時intervals[i]左右端都已確認並依intervals[i-1]的區間對照值進行調整，完成合併後即可拋棄intervals[i-1]。

Code:

class Solution:
    # @param intervals, a list of Intervals
    # @return a list of Interval
    def merge(self, intervals):
        #not sorted yet
        #sort first
        if len(intervals) == 0: return []
        interval_len = len(intervals)
        intervals.sort(key = lambda k: k.start)
        i = 1
        while i = 1 and intervals[i].start <= intervals[i-1].end:
                intervals[i].start = intervals[i-1].start
                if intervals[i].end < intervals[i-1].end:
                    intervals[i].end = intervals[i-1].end
                intervals.pop(i-1)
            else: i += 1
        return intervals

GitHub: GitHub