[Leetcode] 0056. Merge Intervals

Explore diverse LeetCode solutions in Python, C++, JavaScript, SQL, and TypeScript. Ideal for interview prep, learning, and code practice in multiple programming languages. Github Repo Link

內容目錄

Medium

Given an array of intervals where intervals[i] = [start_i, end_i], 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 <= 10⁴
intervals[i].length == 2
0 <= start_i <= end_i <= 10⁴

Python

				
					# time complexity: O(nlogn)
# space complexity: O(n)
from typing import List


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


intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
print(Solution().merge(intervals))
intervals = [[1, 4], [4, 5]]
print(Solution().merge(intervals))
intervals = [[1, 4], [2, 3]]
print(Solution().merge(intervals))
intervals = [[1, 4], [1, 4]]
print(Solution().merge(intervals))

Medium

Python

相關文章