Merge Intervals

📋

Problem

Imagine you have a calendar with multiple booked time slots, and you want to combine overlapping meetings to see your free time clearly.

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

1 ≤ intervals.length ≤ 10^5intervals[i].length == 20 ≤ start_i ≤ end_i ≤ 10^9

Edge cases: Single interval → output is the same single intervalAll intervals non-overlapping → output is the same as inputAll intervals overlapping → output is one merged interval

</>

IDE

def merge(intervals: list[list[int]]) -> list[list[int]]:public int[][] merge(int[][] intervals)vector<vector<int>> merge(vector<vector<int>>& intervals)function merge(intervals)

def merge(intervals):
    # Write your solution here
    pass

class Solution {
    public int[][] merge(int[][] intervals) {
        // Write your solution here
        return new int[0][0];
    }
}

#include <vector>
using namespace std;

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    // Write your solution here
    return {};
}

function merge(intervals) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[1,3],[2,6],[8,10],[15,18]]No merging performed; code returns input as is.✅ Sort intervals by start and merge overlapping intervals by comparing current start with last merged end.

Wrong: [[1,6],[8,10],[15,18],[2,6]]Incorrect merging logic that appends intervals without removing merged ones.✅ When merging, update last merged interval end and do not append duplicates.

Wrong: [[1,3],[2,6],[8,10],[15,18]]Fails to merge intervals touching at boundaries due to strict < comparison.✅ Use <= comparison to merge intervals that touch at boundaries.

Wrong: [[1,4],[5,7],[6,8]]Greedy approach merges only adjacent intervals, missing transitive merges.✅ Sort intervals and merge all overlapping intervals in one pass, not just adjacent pairs.

Wrong: TLE or timeoutNested loops causing O(n^2) time complexity on large inputs.✅ Sort intervals and merge in one pass to achieve O(n log n) time complexity.

✓

Test Cases

Try testing your solution on empty and single interval inputs to ensure base cases are handled.

Consider tricky cases where intervals touch at boundaries or multiple intervals overlap transitively.

Optimize your solution to avoid nested loops; sorting plus one pass merge is the key.

t1_01basic

Input{"intervals":[[1,3],[2,6],[8,10],[15,18]]}

Expected[[1,6],[8,10],[15,18]]

⏱ Performance - must finish in 2000ms

Intervals [1,3] and [2,6] overlap and are merged into [1,6]. The others do not overlap.

💡 Sort intervals by their start times before merging.

💡 Merge intervals by comparing current interval's start with last merged interval's end.

💡 If intervals overlap, update the end of last merged interval to max of both ends.

Why it failed: Failed to merge overlapping intervals correctly; ensure you sort intervals and merge by comparing current start with last merged end.

✓ Correctly merged overlapping intervals using sorting and one-pass merge.

t1_02basic

Input{"intervals":[[1,4],[5,6],[7,8]]}

Expected[[1,4],[5,6],[7,8]]

⏱ Performance - must finish in 2000ms

All intervals are non-overlapping, so output is the same as input.

💡 Check if current interval overlaps with last merged interval.

💡 If no overlap, append current interval to merged list.

💡 Do not merge intervals if current start is greater than last merged end.

Why it failed: Incorrectly merged non-overlapping intervals; fix by only merging when current start <= last merged end.

✓ Correctly identified and preserved non-overlapping intervals.

t2_01edge

Input{"intervals":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input returns empty output.

💡 Consider the case when input list is empty.

💡 Return empty list immediately if no intervals are given.

💡 Check for empty input before processing merges.

Why it failed: Code crashes or returns non-empty output on empty input; add a check to return [] if input is empty.

✓ Handles empty input gracefully by returning empty list.

t2_02edge

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

Expected[[5,5]]

⏱ Performance - must finish in 2000ms

Single interval with same start and end returns itself.

💡 Single interval input should return the same interval.

💡 No merging needed if only one interval is present.

💡 Check that your code handles single-element lists correctly.

Why it failed: Fails on single interval input; ensure code returns input as is when length is 1.

✓ Correctly returns single interval without modification.

t2_03edge

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

Expected[[1,10]]

⏱ Performance - must finish in 2000ms

All intervals overlap within [1,10], merged into one interval.

💡 Check if intervals fully contained within a larger interval are merged correctly.

💡 Merging should extend the end to the maximum end of overlapping intervals.

💡 Ensure your merge logic updates the end boundary properly.

Why it failed: Fails to merge nested intervals into one; fix by updating end to max of current and overlapping intervals.

✓ Correctly merges all overlapping and nested intervals into one.

t3_01corner

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

Expected[[1,4],[5,8]]

⏱ Performance - must finish in 2000ms

Overlapping intervals merged correctly; greedy approach that merges only adjacent intervals fails here.

💡 Sorting intervals by start is essential before merging.

💡 Merging must consider all overlapping intervals, not just adjacent pairs.

💡 Use a stack or result list to merge intervals by comparing current start with last merged end.

Why it failed: Greedy approach merging only adjacent intervals fails; fix by sorting and merging all overlapping intervals in one pass.

✓ Correctly merges all overlapping intervals beyond just adjacent pairs.

t3_02corner

Input{"intervals":[[1,3],[3,5],[6,8]]}

Expected[[1,5],[6,8]]

⏱ Performance - must finish in 2000ms

Intervals touching at boundaries are merged correctly.

💡 Check if intervals that touch at endpoints should be merged.

💡 Use <= comparison for merging intervals, not just <.

💡 Update merge condition to current start <= last merged end.

Why it failed: Fails to merge intervals touching at boundaries; fix by using <= in overlap condition instead of <.

✓ Correctly merges intervals that touch at boundaries.

t3_03corner

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

Expected[[1,5]]

⏱ Performance - must finish in 2000ms

Multiple intervals touching consecutively merged into one.

💡 Ensure merging is transitive across multiple intervals.

💡 Keep updating the end of merged interval as long as overlaps continue.

💡 Do not reset merged interval prematurely.

Why it failed: Fails to merge multiple consecutive touching intervals; fix by continuing merge while current start <= last merged end.

✓ Correctly merges multiple consecutive touching intervals into one.

t4_01performance

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

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 requires O(n log n) sorting and O(n) merging to complete within 2 seconds.

💡 Sorting intervals is O(n log n) and necessary for efficient merging.

💡 Avoid nested loops to prevent O(n^2) time complexity.

💡 Use a single pass after sorting to merge intervals efficiently.

Why it failed: TLE due to nested loops or inefficient merging; fix by sorting intervals and merging in one pass with O(n log n) complexity.

✓ Efficient O(n log n) solution confirmed by passing performance test.

Practice

1. You are given a list of intervals where each interval has a start and end time. Your goal is to select the maximum number of intervals such that none of the selected intervals overlap. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming that tries all subsets of intervals to find the maximum non-overlapping set.

B. Sort intervals by their start time and always pick the earliest starting interval first.

C. Sort intervals by their end time and greedily select intervals that start after the last selected interval ends.

D. Use a graph coloring algorithm to assign intervals to different colors ensuring no overlaps.

Solution

1. Step 1: Understand the problem goal

   The problem requires selecting the maximum number of intervals with no overlaps.

2. Step 2: Identify the optimal greedy strategy

   Sorting intervals by their end time and greedily picking intervals that start after the last selected interval ends ensures the maximum number of intervals are chosen.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Greedy by earliest end time is a classic optimal approach [OK]

Hint: Sort by end time for max non-overlapping intervals [OK]

Common Mistakes:

• Sorting by start time and picking earliest start first
• Trying brute force DP without pruning
• Using graph coloring which is unrelated here

2. The following code attempts to implement the optimal car pooling solution. Which line contains a subtle bug that can cause incorrect capacity checks?

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  # Bug here
    current_passengers = 0
    for i in range(max_location + 1):
        current_passengers += diff[i]
        if current_passengers > capacity:
            return false
    return true

medium

A. Line that increments diff[end] by num instead of decrementing

B. Line that updates max_location in the first loop

C. Line that increments diff[start] by num

D. Line that checks if current_passengers exceeds capacity

Solution

1. Step 1: Understand difference array updates

   Passengers boarding at start location increase count; passengers leaving at end location must decrease count.

2. Step 2: Identify incorrect update

   Line incrementing diff[end] by num adds passengers instead of removing them, causing incorrect capacity calculation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Increment at end location breaks capacity tracking [OK]

Hint: End location must decrement passengers, not increment [OK]

Common Mistakes:

• Incrementing instead of decrementing at end
• Forgetting to update difference array
• Checking capacity before summing passengers

3. Consider this buggy code snippet for removing covered intervals:

def remove_covered_intervals(intervals):
    intervals.sort(key=lambda x: (x[0], x[1]))  # Bug here
    count = 0
    max_end = 0
    for _, end in intervals:
        if end > max_end:
            count += 1
            max_end = end
    return count

What is the bug in this code?

medium

A. The condition 'if end > max_end' should be 'if end >= max_end' to include equal ends.

B. max_end is not updated correctly inside the loop.

C. Sorting by end ascending instead of descending causes coverage detection failure.

D. The nested loop for coverage check is missing, causing incorrect results.

Solution

1. Step 1: Analyze sorting key

   Sorting by (start ascending, end ascending) orders intervals with same start from shortest to longest, which breaks coverage detection.

2. Step 2: Understand coverage detection logic

   Coverage detection relies on intervals with same start being sorted longest first (end descending) so covered intervals come after.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting end ascending causes missed coverage when starts equal [OK]

Hint: Sort end descending to detect coverage correctly [OK]

Common Mistakes:

• Sorting end ascending instead of descending
• Using strict inequality incorrectly

4. Suppose the problem changes: intervals can be reused infinitely many times, and you want to count how many intervals contain each point considering unlimited reuse (e.g., intervals repeat periodically). Which modification to the line sweep approach correctly handles this scenario?

hard

A. No change needed; line sweep already counts intervals correctly regardless of reuse.

B. Preprocess intervals to merge overlapping intervals into one, then run line sweep once.

C. Use a segment tree or binary indexed tree to handle repeated intervals efficiently instead of line sweep.

D. Modify events to include multiple copies of intervals explicitly and run line sweep on expanded events.

Solution

1. Step 1: Understand reuse impact

   Infinite reuse means intervals repeat periodically, so naive line sweep with explicit events cannot handle infinite copies.

2. Step 2: Recognize data structure need

   Segment trees or binary indexed trees can efficiently query counts over ranges and handle repeated intervals without enumerating all copies.

3. Step 3: Why other options fail

   No change (A) ignores infinite reuse; merging (B) loses count detail; explicit expansion (D) is infeasible for infinite repeats.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Segment trees handle range queries with repeated intervals efficiently [OK]

Hint: Infinite reuse requires data structures, not event enumeration [OK]

Common Mistakes:

• Assuming line sweep handles infinite repeats
• Trying to expand events explicitly
• Merging intervals loses count accuracy

5. If employees can have intervals with negative start or end times (e.g., [-5, 0]) or zero-length intervals, which modification to the sweep line algorithm is necessary to correctly find free time?

hard

A. Ignore zero-length intervals and ensure sorting places end events before start events at ties

B. Treat zero-length intervals as free time intervals

C. Sort events only by time, ignoring event type

D. Merge touching intervals as free time gaps

Solution

1. Step 1: Handle zero-length intervals

   Zero-length intervals like [2,2] do not represent busy time and should be ignored to avoid false free intervals.

2. Step 2: Maintain correct sorting order

   Sorting end events before start events at same time prevents reporting free time between touching intervals or zero-length intervals.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring zero-length intervals and correct sorting avoids invalid free times [OK]

Hint: Ignore zero-length intervals and sort end before start events [OK]

Common Mistakes:

• Counting zero-length intervals as free time
• Sorting start before end events