Bird
Raised Fist0
Interview PrepintervalsmediumFacebookAmazonGoogle

Insert Interval

Choose your preparation mode4 modes available
📋
Problem

Imagine you have a calendar with booked time slots and want to add a new meeting without conflicts. How do you insert it and merge overlapping times?

Given a list of non-overlapping intervals sorted by their start time, insert a new interval into the list and merge if necessary. Return the updated list of intervals sorted by start time.

1 ≤ number of intervals ≤ 10^5Intervals are sorted by start timeInterval start and end are integers in range [0, 10^9]New interval's start ≤ end
Edge cases: Empty intervals list → output is just the new intervalNew interval does not overlap and goes before all intervals → inserted at startNew interval does not overlap and goes after all intervals → inserted at end
</>
IDE
def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:public List<int[]> insert(List<int[]> intervals, int[] newInterval)vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval)function insert(intervals, newInterval)
def insert(intervals, newInterval):
    # Write your solution here
    pass
class Solution {
    public List<int[]> insert(List<int[]> intervals, int[] newInterval) {
        // Write your solution here
        return new ArrayList<>();
    }
}
#include <vector>
using namespace std;

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    // Write your solution here
    return {};
}
function insert(intervals, newInterval) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: [[1,3],[2,5],[6,9]]Fails to merge overlapping intervals; inserts newInterval without merging.✅ Merge intervals where intervals[i][0] <= newInterval[1] by updating newInterval boundaries.
Wrong: [[5,7]]Fails on empty intervals input; returns only newInterval but ignores empty list condition.✅ Return [newInterval] if intervals list is empty.
Wrong: [[1,2],[3,5],[6,7],[8,10],[12,16],[4,8]]Appends newInterval at end without merging overlapping intervals.✅ Merge all overlapping intervals before appending newInterval.
Wrong: [[1,2],[3,5],[6,7],[8,10],[12,16]]Fails to insert newInterval when it does not overlap any intervals.✅ Insert newInterval in correct position when no overlaps.
Wrong: [[1,2],[3,8],[12,16]]Stops merging after first overlap (greedy trap).✅ Continue merging while intervals overlap newInterval.
✓
Test Cases
t1_01basic
Input{"intervals":[[1,3],[6,9]],"newInterval":[2,5]}
Expected[[1,5],[6,9]]

The new interval overlaps with [1,3], so they merge into [1,5]. The interval [6,9] remains unchanged.

t1_02basic
Input{"intervals":[[1,2],[3,5],[6,7],[8,10],[12,16]],"newInterval":[4,8]}
Expected[[1,2],[3,10],[12,16]]

New interval overlaps with [3,5],[6,7],[8,10], merged into [3,10]. Others remain unchanged.

t2_01edge
Input{"intervals":[],"newInterval":[5,7]}
Expected[[5,7]]

Empty intervals list; output is just the new interval.

t2_02edge
Input{"intervals":[[10,12]],"newInterval":[1,5]}
Expected[[1,5],[10,12]]

New interval does not overlap and goes before all intervals; inserted at start.

t2_03edge
Input{"intervals":[[1,2],[3,4]],"newInterval":[5,7]}
Expected[[1,2],[3,4],[5,7]]

New interval does not overlap and goes after all intervals; inserted at end.

t3_01corner
Input{"intervals":[[2,3],[5,7],[8,10]],"newInterval":[1,11]}
Expected[[1,11]]

New interval overlaps all intervals; merged into one big interval.

t3_02corner
Input{"intervals":[[1,2],[3,5],[6,7],[8,10],[12,16]],"newInterval":[4,8]}
Expected[[1,2],[3,10],[12,16]]

Tests greedy trap: merging only first overlapping interval instead of all overlapping intervals.

t3_03corner
Input{"intervals":[[1,3],[6,9]],"newInterval":[2,5]}
Expected[[1,5],[6,9]]

Tests off-by-one error in overlap condition (e.g., using < instead of <=).

t4_01performance
Input{"_description":"n=100000 at constraint boundary - executor generates this input"}
⏱ Performance - must finish in 2000ms

n=100000 intervals, O(n) solution must complete within 2 seconds.

Practice

(1/5)
1. Consider the following Python code implementing the optimal car pooling solution. What is the return value when called with trips = [[2,1,5],[3,3,7]] and capacity = 4?
def carPooling(trips, capacity):
    max_location = 0
    for _, start, end in trips:
        max_location = max(max_location, end)
    diff = [0] * (max_location + 1)
    for num, start, end in trips:
        diff[start] += num
        diff[end] -= num
    current_passengers = 0
    for i in range(max_location + 1):
        current_passengers += diff[i]
        if current_passengers > capacity:
            return false
    return true

print(carPooling([[2,1,5],[3,3,7]], 4))
easy
A. Error due to index out of range
B. true
C. false
D. true only if capacity is at least 5

Solution

  1. Step 1: Build difference array

    diff after processing trips: diff[1]+=2, diff[5]-=2, diff[3]+=3, diff[7]-=3
  2. Step 2: Sweep through diff to track passengers

    At location 1: current_passengers=2; at 3: current_passengers=5 (2+3), which exceeds capacity=4 -> return false
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Passenger count exceeds capacity at location 3 [OK]
Hint: Sum diffs to track passengers, check capacity [OK]
Common Mistakes:
  • Off-by-one in diff array indexing
  • Checking capacity only at trip start
  • Forgetting to decrement at trip end
2. Given multiple employees' schedules with intervals representing their busy times, which algorithmic approach guarantees finding all common free time intervals where no employee is busy?
easy
A. Greedy interval scheduling that picks earliest finishing intervals
B. Dynamic programming to find maximum non-overlapping intervals
C. Sweep line / event processing that tracks interval start and end events
D. Brute force checking every time point across all intervals

Solution

  1. Step 1: Understand problem requires identifying gaps where no intervals overlap

    Greedy scheduling or DP focus on selecting intervals, not gaps between them.
  2. Step 2: Sweep line processes all start/end events in order, tracking active intervals to find free gaps

    This approach efficiently detects when no employee is busy, yielding correct free times.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sweep line tracks active intervals and finds free gaps [OK]
Hint: Sweep line tracks interval endpoints to find free gaps [OK]
Common Mistakes:
  • Assuming greedy or DP can find free gaps directly
3. The following code attempts to count intervals containing each point using a line sweep. Identify the bug that causes incorrect counts for points exactly at interval ends.
medium
A. Line adding interval end event should use end + 1 instead of end.
B. Sorting key should sort points before interval starts.
C. Active count should be incremented after processing points, not before.
D. Result array initialization size is incorrect.

Solution

  1. Step 1: Identify event creation for interval ends

    Interval end events use 'end' instead of 'end + 1', so points exactly at interval end are processed after the interval ends.
  2. Step 2: Understand effect on counting

    Because end events are processed at 'end', points at 'end' see active count after decrement, missing that interval.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Changing to end + 1 fixes counting for points at interval ends [OK]
Hint: Interval end event must be at end+1 to include points at end [OK]
Common Mistakes:
  • Using end instead of end+1
  • Misordering events
  • Incorrect active count update
4. What is the time complexity of the addNum operation in the optimal balanced tree approach for maintaining disjoint intervals, assuming there are n intervals stored?
medium
A. O(n) because intervals need to be scanned linearly for merging
B. O(log n) due to binary search and limited merging operations
C. O(n log n) because each insertion requires sorting intervals
D. O(1) since insertion is always at the end or start

Solution

  1. Step 1: Identify main operations in addNum

    addNum uses binary search (bisect_left) to find insertion index in O(log n).
  2. Step 2: Analyze merging cost

    Merging involves at most constant number of interval merges (left, right, or both), so O(1) extra work.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Binary search dominates, merges are constant time [OK]
Hint: Binary search + constant merges -> O(log n) [OK]
Common Mistakes:
  • Assuming linear scan for merging
  • Confusing sorting cost per insertion
  • Ignoring constant merge steps
5. Examine the following buggy code for Employee Free Time. Which line contains the subtle bug causing incorrect free time intervals?
medium
A. Line appending end event with (interval[1], -1)
B. Line appending start event with (interval[0], 1)
C. Line updating prev = time inside loop
D. Line sorting events with key=lambda x: (x[0], -x[1])

Solution

  1. Step 1: Understand sorting order impact

    End events must come before start events at same time to avoid false free intervals.
  2. Step 2: Identify bug in sorting key

    Sorting with key (x[0], -x[1]) puts start events before end events at ties, causing incorrect free time detection.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Correct sorting is (x[0], x[1]) to put end events before start [OK]
Hint: End events must sort before start events at same time [OK]
Common Mistakes:
  • Sorting start before end events at same timestamp
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard