Insert Interval - codepath/compsci_guides GitHub Wiki
TIP102 Unit 1 Session 2 Advanced (Click for link to problem statements)
Problem Highlights
- 💡 Difficulty: Easy
- ⏰ Time to complete: 10 mins
- 🛠️ Topics: Arrays, Sorting, Merging Intervals
U-nderstand
Understand what the interviewer is asking for by using test cases and questions about the problem.
-
Q: What is the input to the function?
- A: The input consists of a list of non-overlapping intervals
intervals
, sorted in ascending order, and a new intervalnew_interval
that needs to be inserted.
- A: The input consists of a list of non-overlapping intervals
-
Q: What is the expected output of the function?
- A: The function should return a new list of intervals where the
new_interval
has been inserted and any overlapping intervals have been merged.
- A: The function should return a new list of intervals where the
-
Q: What does it mean for intervals to overlap?
- A: Two intervals
[a, b]
and[c, d]
overlap ifb >= c
anda <= d
. Overlapping intervals should be merged into a single interval.
- A: Two intervals
-
Q: What if the new interval does not overlap with any existing interval?
- A: If the new interval does not overlap with any existing interval, it should be inserted in its correct position based on the start time.
-
Q: What should the function return if
intervals
is empty?- A: If
intervals
is empty, the function should return a list containing just thenew_interval
.
- A: If
-
The function insert_interval() should insert a new interval into a list of non-overlapping intervals and merge any overlapping intervals.
HAPPY CASE
Input: intervals = [1, 3], [6, 9](/codepath/compsci_guides/wiki/1,-3],-[6,-9), new_interval = [2, 5]
Expected Output: [1, 5], [6, 9](/codepath/compsci_guides/wiki/1,-5],-[6,-9)
UNHAPPY CASE
Input: intervals = [1, 2], [3, 5], [6, 7], [8, 10], [12, 16](/codepath/compsci_guides/wiki/1,-2],-[3,-5],-[6,-7],-[8,-10],-[12,-16), new_interval = [4, 8]
Expected Output: [1, 2], [3, 10], [12, 16](/codepath/compsci_guides/wiki/1,-2],-[3,-10],-[12,-16)
EDGE CASE
Input: intervals = [], new_interval = [5, 7]
Expected Output: [5, 7](/codepath/compsci_guides/wiki/5,-7)
P-lan
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Iterate through the existing intervals and handle them based on their relation to the new interval.
1. Initialize an empty list `merged` to store the resulting intervals.
2. Initialize an index `i` to 0 and get the length `n` of `intervals`.
3. Add all intervals that end before the new interval starts to `merged`.
4. Merge intervals that overlap with the new interval:
a. Update the start and end of the new interval based on the overlapping intervals.
5. Append the merged new interval to `merged`.
6. Add any remaining intervals to `merged`.
7. Return `merged`
⚠️ Common Mistakes
- Failing to properly merge overlapping intervals.
- Not handling edge cases like inserting into an empty list or merging at the beginning or end.
I-mplement
Implement the code to solve the algorithm.
def insert_interval(intervals, new_interval):
merged = []
i = 0
n = len(intervals)
# Add all intervals that come before the new interval
while i < n and intervals[i][1] < new_interval[0]:
merged.append(intervals[i])
i += 1
# Merge intervals that overlap with the new interval
while i < n and intervals[i][0] <= new_interval[1]:
new_interval[0] = min(new_interval[0], intervals[i][0])
new_interval[1] = max(new_interval[1], intervals[i][1])
i += 1
merged.append(new_interval)
# Add the remaining intervals
while i < n:
merged.append(intervals[i])
i += 1
return merged