Leetcode 56. Merge Intervals

Merge Intervals : 此題的意思就是給你一格個Interval的集合，去找到他相交的區間，然後最後合併完成後，他們之前是沒有交集的。

解法 :

如果前一個list的最後的值大於等於後一個list的初始值(前一個list長度不能包含後一個list)，則表示有交集，merge兩個list

時間複雜度 : O(n logn)

空間複雜度 : O(n)

Python

1. 將區域間從左到右進行排列。

2. 依次處理每個區域，如果當前區間的左端點大於等於前一個區間的右端點，則說明這兩個區域沒有重疊，將當前區間加入暫存list(ans)。

3. 如果當前區域的左端點小於前一個區域的右端點，則說明這兩個區域間有重疊，將當前區域的右端點取代為當前區域的左端點和前一個區域的右端點的最大值

class Solution(object):
    def merge(self, intervals):
			if len(intervals) == 0:
	            return []
	        intervals.sort(key=lambda x: x.start)       #左到右進行排列
	        ans = []
	        cur = intervals[0]     
	        for i in range(1, len(intervals)):
	            if intervals[i].start <= cur.end:             #情況3.
	                cur.end = max(cur.end, intervals[i].end)
	            else:
	                ans.append(cur)                           #情況2.
	                cur = intervals[i]
     ans.append(cur)
     return ans

C++

對原始區間按照起始位置進行排序，從第一個區間開始，如果當前區間的起始位置小於等於已合併區間的結束位置，則更新已合併區間的結束位置為兩個區間結束位置的最大值；否則，將當前區間加入已合併區間序列中；返回已合併區間序列。
時間複雜度為O(nlogn)，空間複雜度為O(n)

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() <= 1) return intervals;
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        merged.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] <= merged.back()[1]) {
                merged.back()[1] = max(merged.back()[1], intervals[i][1]);
            } else {
                merged.push_back(intervals[i]);
            }
        }
        return merged;
    }
};