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 <= 10^4intervals[i].length == 20 <= starti <= endi <= 10^4
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# Sort intervals based on the start time
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
# if the list of merged intervals is empty or if the current
# interval does not overlap with the previous, simply append it.
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
# there is overlap, so we merge the current and previous intervals.
merged[-1][1] = max(merged[-1][1], interval[1])
return mergedO(nlogn), where n is the number of intervals. The sorting of intervals takes O(nlogn) and the merging process takes O(n). Thus, the dominating factor is the sorting step.
O(logn) or O(n), depending on the implementation of the sort in Python. The space required for sorting. O(n) space is for the output list merged.