Merge Intervals
- 3 min read
- Interval
- LC-Medium
3 years ago
Solution
| Time | Space | Explanation |
|---|---|---|
O(n log n) | O(1) |
- YOU CANNOT USE THE SAME CODE STRUCTURE AS IN Insert Interval, because in Insert Interval, you only add one interval
- Once that interval is dealt with, you would immediately return after accounting for other itervals
- Here, you cannot do that since there might be some further merging you need to do
- So instead of curInterval being a variable, your curInterval would be the last element in the output array
- Sort the intervals by first value
- Initialize answer list with first sorted interval
- Iterate through rest of intervals. You will always compared the current interval with the last interval in the answer list (
ans[-1])there are two possible cases:- The current interval starts after the existing interval (in the answer list) ends. In this case, just add the current interval to the answer list
- The intervals overlap. In this case, replace the last interval in the answer list with the merged interval
- The third case, that was possible in Insert Interval isn't possible here, because we sort the list
- What's the third case? Existing interval in answer list starts after the current interval. Not possible, since we sorted the lists by start value of the interval
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda interval: interval[0])
ans = [intervals[0]]
for i in range(1, len(intervals)):
if intervals[i][0] <= ans[-1][1]:
ans[-1] = [min(intervals[i][0], ans[-1][0]), max(intervals[i][1], ans[-1][1])]
else:
ans.append(intervals[i])
return ans
My First Solution -Kinda Bad?
-
First thoughts without looking at the solution- was an interesting problem. I'm happy I was able to solve it.
-
I didn't know that in Insert Interval, the intervals were sorted. I was surprised when they weren't sorted here.
-
So... I sorted it myself. That brings the TC to O(n log n) but whatever. There's probably an O(n) solution.
-
Thoughts after looking at the Neetcode video: Damn, you did have to sort it. So I got the optimal solution on the first try. Fuck yeah.
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if len(intervals) == 1:
return intervals
intervals = sorted(intervals, key=lambda x: x[0])
ans = []
cur_interval = intervals[0]
for i in range(1, len(intervals)):
# If overlapping, merge intervals and set as cur interval
if intervals[i][0] <= cur_interval[1]:
cur_interval = [min(intervals[i][0], cur_interval[0]), max(intervals[i][1], cur_interval[1])]
if i == len(intervals) - 1:
ans.append(cur_interval)
# If not overlapping, add current interval to answer and set cur interval to next interval
else:
ans.append(cur_interval)
# if i + 1 < len(intervals):
cur_interval = intervals[i]
if i == len(intervals) - 1: # if last element and not overlapping, append interval to answer.
ans.append(intervals[i])
i += 1
return ans