Intuition
- Visualize the 3 different ways of overlap
- Have a start and end which denotes the current merge you will have in your final solution of interval
- Go through and follow the rules you set for each case (very brute force way)
- Then simplify your code after it passes the test cases
- Sort by start time to handle a large set of permutations wherein the interval does not start before the next one.
Question
How is it possible to do this with only one for loop iteration?
- That is because we are handling each case of merge in one step by handling all cases where a merge is possible, and since the intervals are sorted by start time, each interval is either consumed or ignored, resulting in the final array.
Runtime
- where N is the size of the interval
- Space is an extra since I am using another array to compute the intervals without messing with my for loop indexing.
Code
Clean
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
new_intervals = []
start, end = intervals[0][0], intervals[0][1]
for i in range(1, len(intervals)):
compare_start, compare_end = intervals[i][0], intervals[i][1]
if end >= compare_start and end <= compare_end:
if end <= compare_end:
end = compare_end
elif end < compare_start:
new_intervals.append([start, end])
start, end = compare_start, compare_end
new_intervals.append([start, end])
return new_intervals Verbose
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
new_intervals = []
start, end = intervals[0][0], intervals[0][1]
for i in range(1, len(intervals)):
compare_start, compare_end = intervals[i][0], intervals[i][1]
if end >= compare_start and end >= compare_end:
continue
elif end >= compare_start and end <= compare_end:
end = compare_end
elif end < compare_start:
new_intervals.append([start, end])
start, end = compare_start, compare_end
else:
print("Logical Issue")
new_intervals.append([start, end])
return new_intervals