1. Brute Force Approach
A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from the list and merge the other into the first interval. Repeat the same steps for the remaining intervals after the first.
Time Complexity: O(n²)
Space Complexity: O(n)
The idea to solve this problem is, first sort the intervals according to the starting time. Once we have the sorted intervals, we can combine all intervals in a linear traversal. The idea is, in sorted array of intervals, if interval[i] doesn’t overlap with interval[i-1], then interval[i+1] cannot overlap with interval[i-1] because starting time of interval[i+1] must be greater than or equal to interval[i].
LeetCode 56 - Merge Intervals [medium]
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.
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if len(intervals) == 0:
return []
intervals = sorted(intervals, key = lambda x: x[0])
result = [intervals[0]]
for interval in intervals[1:]:
if interval[0] <= result[-1][1]:
result[-1][1] = max(interval[1], result[-1][1])
else:
result.append(interval)
return result
Time complexity: O(N*log(N))
Auxiliary Space: O(N)
We iterate the list once so the total cost will be O(N log N) because the sort function in python is O(N log N).
2.Solution:
Follow the steps mentioned below to implement the approach:
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
def overlap(a, b):
if a[1] >= b[0] and b[1] >= a[0]:
return True
else:
return False
i = 0
intervals=sorted(intervals)
while i < (len(intervals) - 1):
if overlap(intervals[i],intervals[i + 1]):
intervals[i]=[min(intervals[i][0],intervals[i + 1][0]),max(intervals[i][1],intervals[i + 1][1])]
intervals.remove(intervals[i + 1])
else:
i += 1
return intervals
Time Complexity: O(N * log N) where N is the total number of intervals. In the beginning, since we sort the intervals, our algorithm will take O(N * log N) to run.
This approach is quite useful when dealing with intervals, overlapping items, or merging intervals.