[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

Table of contents

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

related articles