56. Merge Intervals

[fockspaces]

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. Example 2:

Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

1 <= intervals.length <= 104 intervals[i].length == 2 0 <= starti <= endi <= 104

[fockspaces]

一開始先推入第一個interval進ans 之後不斷拿ans最尾端區間比較是否與下一個interval重疊 有重疊就更新ans尾端，沒有就直接將interval推入

這題要想到拿ans.back()來比較

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ans;

        for(auto interval : intervals) {
            if(ans.size() == 0) {ans.push_back(interval); continue;}
            if(ans.back()[1] >= interval[0]) 
                ans.back()[1] = max(ans.back()[1], interval[1]);
            else ans.push_back(interval);
        }
        return ans;
    }
};

[fockspaces]

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ans = []
        intervals.sort()
        for interval in intervals:
            if not ans or interval[0] > ans[-1][1]:
                ans.append(interval)
            else:
                ans[-1][0] = min(ans[-1][0], interval[0])
                ans[-1][1] = max(ans[-1][1], interval[1])
        return ans

[MingFaTW]

Time: O(NlogN) + O(N)

Space: O(N)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals = sorted(intervals)
        results = [intervals[0]]

        for interval in intervals[1:]:
            if self.is_overlapped(interval, results[-1]):
                results[-1] = self._merge(interval, results[-1])
            else:
                results.append(interval)

        return results

    def is_overlapped(self, new_interval, prev_interval):
        return new_interval[0] <= prev_interval[1]

    def _merge(self, new_interval, original_interval):
        head = min(original_interval[0], new_interval[0])
        tail = max(original_interval[1], new_interval[1])
        return [head, tail]