Leetcode 56. Merge Intervals

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

If you pursue better time complexity, then the key is sorting first, so we only need to judge the lastest element in result list and see if the element’s high is greater than current element’s low. Then the time complexity will be O(nlogn + n) == O(nlogn)

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

        result = [intervals[0]]

        intervals.pop(0)

        for low, high in intervals:
            if result[-1][1] >= low:
                result[-1][1] = max(result[-1][1], high)
            else:
                result.append([low, high])


        return result

My first try didn’t sort at beginning, so the worst case can be O(n^2)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        result = []
        for low, high in intervals:
            if len(result) != 0:
                index = 0
                while index < len(result):
                    if result[index][0] > high or result[index][1] < low:
                        index += 1
                    else:
                        low = min(result[index][0], low)
                        high = max(result[index][1], high)
                        result.pop(index)
                result.append([low, high])
            else:
                result.append([low, high])


        return result