Insert Interval

📋

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
}

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

Focus on handling empty and boundary cases to solidify your base logic.

Test your code against tricky merges and off-by-one overlap conditions.

Optimize your solution to run in linear time for large inputs.

t1_01basic

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

Expected[[1,5],[6,9]]

⏱ Performance - must finish in 2000ms

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

💡 Consider intervals before, overlapping, and after the new interval.

💡 Use two while loops: one to add intervals before newInterval, one to merge overlapping intervals.

💡 Update newInterval start/end while merging, then append it and remaining intervals.

Why it failed: Failed to merge overlapping intervals correctly; fix by updating newInterval boundaries while merging overlapping intervals.

✓ Correctly merges overlapping intervals and inserts new interval.

t1_02basic

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

Expected[[1,2],[3,10],[12,16]]

⏱ Performance - must finish in 2000ms

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

💡 Identify all intervals overlapping with newInterval.

💡 Merge all overlapping intervals into one by updating start and end.

💡 Append merged interval and remaining intervals after merging.

Why it failed: Incorrect merging of multiple overlapping intervals; fix by merging all intervals where start <= newInterval end.

✓ Correctly merges multiple overlapping intervals into one.

t2_01edge

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

Expected[[5,7]]

⏱ Performance - must finish in 2000ms

Empty intervals list; output is just the new interval.

💡 Check if intervals list is empty before processing.

💡 If empty, simply return list containing newInterval.

💡 Avoid loops when intervals is empty to prevent errors.

Why it failed: Fails on empty intervals input; fix by returning [newInterval] if intervals is empty.

✓ Handles empty intervals list correctly by returning newInterval alone.

t2_02edge

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

Expected[[1,5],[10,12]]

⏱ Performance - must finish in 2000ms

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

💡 Check intervals that end before newInterval starts to add them first.

💡 If no overlap, insert newInterval before intervals starting after it.

💡 Ensure order is maintained after insertion.

Why it failed: Fails to insert newInterval before all intervals when no overlap; fix by adding intervals with end < newInterval start first.

✓ Correctly inserts newInterval before all intervals when no overlap.

t2_03edge

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

Expected[[1,2],[3,4],[5,7]]

⏱ Performance - must finish in 2000ms

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

💡 Add all intervals that end before newInterval starts.

💡 If newInterval starts after all intervals, append it at the end.

💡 No merging needed if no overlaps.

Why it failed: Fails to append newInterval at the end when no overlap; fix by appending newInterval after all intervals if no overlap.

✓ Correctly appends newInterval at the end when no overlap.

t3_01corner

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

Expected[[1,11]]

⏱ Performance - must finish in 2000ms

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

💡 Check if newInterval overlaps multiple intervals spanning entire list.

💡 Merge all overlapping intervals into one by updating boundaries.

💡 Return single merged interval if all intervals overlap.

Why it failed: Fails to merge all overlapping intervals into one; fix by merging all intervals where start <= newInterval end and end >= newInterval start.

✓ Correctly merges newInterval overlapping all intervals into one.

t3_02corner

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

Expected[[1,2],[3,10],[12,16]]

⏱ Performance - must finish in 2000ms

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

💡 Do not stop merging after first overlap; continue while intervals overlap newInterval.

💡 Update newInterval boundaries to cover all overlapping intervals.

💡 Append merged interval after processing all overlaps.

Why it failed: Stops merging after first overlap (greedy trap); fix by continuing merge while intervals overlap newInterval.

✓ Correctly merges all overlapping intervals, avoiding greedy trap.

t3_03corner

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

Expected[[1,5],[6,9]]

⏱ Performance - must finish in 2000ms

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

💡 Check overlap condition carefully: intervals[i][0] <= newInterval[1].

💡 Use <= to include intervals that start exactly at newInterval end.

💡 Incorrect condition causes missing merges.

Why it failed: Off-by-one in overlap condition causes missed merges; fix by using intervals[i][0] <= newInterval[1] in merge loop.

✓ Correct overlap condition includes intervals starting exactly at newInterval end.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

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

💡 Use a single pass linear scan to insert and merge intervals.

💡 Avoid sorting or nested loops to meet time constraints.

💡 Pre-allocate result list and minimize operations inside loops.

Why it failed: TLE due to O(n log n) or worse complexity; fix by implementing O(n) single pass merge approach.

✓ Solution runs in O(n) time, passing performance constraints.

Practice

1. Given two lists of closed intervals, each sorted and non-overlapping within themselves, you need to find all intervals where the two lists overlap. Which approach guarantees an optimal time complexity solution?

easy

A. Use a brute force nested loop to compare every interval in the first list with every interval in the second list.

B. Use two pointers to traverse both lists simultaneously, advancing the pointer with the smaller interval endpoint to find intersections efficiently.

C. Sort all intervals from both lists together and then merge overlapping intervals to find intersections.

D. Use dynamic programming to store and compute overlapping intervals between the two lists.

Solution

1. Step 1: Understand problem constraints

   Both lists are sorted and non-overlapping internally, so a linear scan is possible.

2. Step 2: Identify the optimal approach

   Two pointers allow simultaneous traversal, comparing intervals in O(m + n) time, advancing pointers based on interval endpoints.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers avoid unnecessary comparisons and achieve linear time [OK]

Hint: Two pointers exploit sorted order for linear time [OK]

Common Mistakes:

• Assuming brute force is acceptable
• Thinking sorting combined lists is needed
• Misapplying DP to interval intersection

2. You are given a list of meeting time intervals consisting of start and end times. Your task is to find the minimum number of conference rooms required so that all meetings can be held without overlap. Which of the following approaches guarantees an optimal solution with efficient time complexity?

easy

A. Sort intervals by start time and use a min-heap to track the earliest ending meeting to reuse rooms efficiently.

B. Use a brute force approach checking every pair of intervals for overlap and counting maximum overlaps.

C. Use dynamic programming to find the maximum number of non-overlapping intervals and subtract from total intervals.

D. Sort intervals by end time and greedily assign rooms without tracking ongoing meetings.

Solution

1. Step 1: Understand the problem requires tracking overlapping intervals to find minimum rooms.

   Brute force checks all pairs but is inefficient; greedy by end time alone doesn't track concurrent overlaps.

2. Step 2: Recognize that sorting by start time and using a min-heap to track earliest ending meeting allows reusing rooms optimally.

   This approach efficiently manages room allocation by freeing rooms as meetings end.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap approach is standard optimal solution for this problem [OK]

Hint: Min-heap tracks earliest end to reuse rooms efficiently [OK]

Common Mistakes:

• Assuming greedy by end time alone suffices
• Thinking brute force is efficient enough
• Confusing DP for interval scheduling with room allocation

3. What is the time complexity of the optimal greedy algorithm that sorts balloons by their end coordinate and then iterates once to find the minimum number of arrows?

medium

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

Solution

1. Step 1: Identify sorting cost

   Sorting n intervals by end coordinate takes O(n log n) time.

2. Step 2: Identify iteration cost

   Single pass through sorted intervals is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Dominant cost is sorting, so total is O(n log n) [OK]

Hint: Sorting dominates; iteration is linear [OK]

Common Mistakes:

• Assuming linear time because of single pass
• Confusing with brute force O(n^2)
• Ignoring sorting cost

4. What is the time complexity of the optimal greedy algorithm that finds the maximum number of non-overlapping intervals by sorting intervals and iterating through them once?

medium

A. O(n log n) due to sorting plus O(n) iteration, total O(n log n)

B. O(n^2) due to nested comparisons between intervals

C. O(n) since it only iterates once through the intervals

D. O(n log n) because of sorting intervals by start or end time

Solution

1. Step 1: Identify sorting cost

   Sorting intervals by start or end time takes O(n log n) time.

2. Step 2: Identify iteration cost

   Iterating through the sorted intervals to select non-overlapping ones takes O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates, total complexity is O(n log n) [OK]

Hint: Sorting dominates time complexity in interval scheduling [OK]

Common Mistakes:

• Assuming iteration alone is O(n) and ignoring sorting
• Mistaking nested loops causing O(n^2)
• Confusing sorting and iteration costs

5. Suppose the meeting intervals can be reused multiple times (i.e., a meeting can be attended multiple times if no overlaps occur). Which modification to the algorithm is necessary to correctly determine if a person can attend all meetings without overlap?

hard

A. Sort intervals by end time and greedily select intervals to maximize non-overlapping meetings.

B. No change needed; the original algorithm already handles reuse correctly.

C. Use a frequency map to count how many times each interval appears and check overlaps accordingly.

D. Sort intervals by start time and check overlaps as before, but also track counts of repeated intervals.

Solution

1. Step 1: Understand reuse scenario

   Reusing intervals means attending multiple instances of the same meeting, so we want to maximize the number of non-overlapping meetings.

2. Step 2: Identify correct approach

   Sorting by end time and greedily selecting earliest finishing meetings maximizes non-overlapping intervals, handling reuse correctly.

3. Step 3: Why other options fail

   Original algorithm only checks if all intervals can be attended once; frequency maps or tracking counts do not solve scheduling conflicts optimally.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Greedy by end time is classic interval scheduling for maximum non-overlapping intervals [OK]

Hint: Reuse requires interval scheduling by end time [OK]

Common Mistakes:

• Assuming original overlap check suffices for reuse
• Trying to track counts without scheduling logic