Bird
Raised Fist0
Interview PrepintervalsmediumAmazonGoogleFacebookBloomberg

Non-overlapping Intervals (Max Non-Overlap)

Choose your preparation mode4 modes available
▶
Steps
setup

Sort intervals by start time

The intervals are sorted by their start times to process them in chronological order.

💡 Sorting ensures we consider intervals in the order they begin, which is essential for the greedy approach.
Line:intervals.sort(key=lambda x: x[0])
💡 Sorting by start time sets the stage for comparing intervals sequentially.
📊
Non-overlapping Intervals (Max Non-Overlap) - Watch the Algorithm Execute, Step by Step
Watching each comparison and pointer update helps you understand how the greedy choice is made to keep intervals with the earliest end time, which is key to maximizing non-overlapping intervals.
Step 1/10
·Active fill★Answer cell
move_right
[1,3]
0
[2,4]
1
[3,5]
2
record
i
[1,3]
0
[2,4]
1
[3,5]
2
Result: 0
move_right
[1,3]
0
i
[2,4]
1
[3,5]
2
Result: 0
compare
[1,3]
0
i
[2,4]
1
[3,5]
2
Result: 0
shrink
[1,3]
0
i
[2,4]
1
[3,5]
2
Result: 1
move_right
[1,3]
0
[2,4]
1
i
[3,5]
2
Result: 1
compare
[1,3]
0
[2,4]
1
i
[3,5]
2
Result: 1
move_right
[1,3]
0
[2,4]
1
i
[3,5]
2
Result: 1
record
[1,3]
0
[2,4]
1
[3,5]
2
Result: 2
record
[1,3]
0
[2,4]
1
[3,5]
2
Result: 2

Key Takeaways

✓ Sorting intervals by start time allows sequential overlap checks.

Without sorting, the algorithm cannot reliably detect overlaps in order.

✓ When intervals overlap, removing the one with the later end time maximizes future interval inclusion.

This greedy choice is subtle and best understood visually by seeing last_end update.

✓ The final answer is total intervals minus removals, representing the maximum non-overlapping set.

This formula is simple but the reasoning behind removals is clearer when traced step-by-step.

Practice

(1/5)
1. Consider the following code snippet implementing the sweep line approach for Employee Free Time. Given the input schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]], what is the final returned list of free time intervals?
easy
A. [[3,4],[6,10]]
B. [[3,4]]
C. [[3,4],[6,7]]
D. [[3,4],[6,10]]

Solution

  1. Step 1: Sort events and track active intervals

    Events: (1,1),(1,1),(2,-1),(3,-1),(4,1),(5,1),(6,-1),(10,-1). Active counts track busy employees.
  2. Step 2: Identify free intervals when active==0 between events

    Free time occurs between 3 and 4 only, as after 4 active increments again until 10.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Only [3,4] is free time interval [OK]
Hint: Free time only when no active intervals between events [OK]
Common Mistakes:
  • Including intervals after 6 incorrectly as free time
2. Consider the following Python function for interval intersections:
from typing import List

def intervalIntersection(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    i, j = 0, 0
    result = []
    while i < len(A) and j < len(B):
        if A[i][1] < B[j][0]:
            i += 1
        elif B[j][1] < A[i][0]:
            j += 1
        else:
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            result.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
    return result

A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
print(intervalIntersection(A, B))
What is the final output printed by this code?
easy
A. [[1,2],[5,5],[8,10],[15,23],[24,25],[25,26]]
B. [[1,2],[5,5],[8,10],[15,23],[24,25],[25,25]]
C. [[1,2],[5,5],[8,10],[15,23],[24,24],[25,26]]
D. [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Solution

  1. Step 1: Trace first intersection

    Compare [0,2] and [1,5]: overlap is [1,2], add to result.
  2. Step 2: Advance pointers and find all intersections

    Following pointer moves and overlaps yield [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Matches manual step-by-step intersection results [OK]
Hint: Trace pointer increments carefully to avoid off-by-one errors [OK]
Common Mistakes:
  • Including intervals beyond intersection
  • Merging adjacent but non-overlapping intervals
  • Off-by-one in pointer increments
3. What is the time complexity of the optimal in-place merge intervals algorithm that first sorts the intervals and then merges them in one pass?
medium
A. O(n log n) due to the sorting step dominating the runtime
B. O(n) because merging is done in a single pass
C. O(n²) because each interval is compared with all others during merging
D. O(n log n) because merging requires binary searches for overlaps

Solution

  1. Step 1: Identify the sorting step complexity.

    Sorting n intervals by start time takes O(n log n) time.
  2. Step 2: Analyze the merging step complexity.

    Merging intervals in one pass is O(n), which is dominated by sorting.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sorting dominates overall complexity, merging is linear. [OK]
Hint: Sorting dominates, merging is linear [OK]
Common Mistakes:
  • Ignoring sorting cost
  • Assuming nested comparisons cause O(n²)
4. The following code attempts to merge intervals in-place after sorting. Identify the line that contains a subtle bug causing incorrect results on some inputs.
medium
A. Line 3: intervals.sort(key=lambda x: x[0])
B. Line 9: intervals[index][1] = max(intervals[index][1], intervals[i][1])
C. Line 12: return intervals # missing slicing after in-place merge
D. Line 8: if intervals[i][0] <= intervals[index][1]:

Solution

  1. Step 1: Understand the in-place merge modifies intervals up to index.

    After merging, only intervals[:index+1] are valid merged intervals.
  2. Step 2: Identify the bug in the return statement.

    Returning the entire intervals list without slicing includes extra unmerged intervals, causing incorrect output.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Return intervals[:index+1] to exclude leftover intervals. [OK]
Hint: Return sliced intervals after in-place merge [OK]
Common Mistakes:
  • Forgetting to slice after in-place merge
  • Modifying list while iterating without adjusting index
5. Suppose meetings can be scheduled with negative start or end times (e.g., representing times before a reference point). Which modification to the min-heap approach is necessary to correctly compute the minimum number of meeting rooms?
hard
A. Adjust the comparison in the heap to handle negative end times by using a max-heap instead of min-heap.
B. Sort intervals by absolute value of start times to handle negative values correctly.
C. Sort intervals normally by start time and use the min-heap approach as usual; negative times do not affect logic.
D. No modification needed; the existing min-heap approach works regardless of negative times.

Solution

  1. Step 1: Understand sorting by start time works with negative values.

    Sorting by start time orders intervals correctly even if times are negative.
  2. Step 2: Confirm min-heap logic remains valid.

    Heap tracks earliest end time; negative values do not affect min-heap property or comparison logic.
  3. Step 3: No need for absolute value sorting or max-heap.

    Using absolute values or max-heap breaks the logic of interval ordering and room reuse.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Negative times do not change sorting or heap logic [OK]
Hint: Sorting by start time works even with negative times [OK]
Common Mistakes:
  • Sorting by absolute values breaks interval order
  • Switching to max-heap unnecessarily
  • Assuming negative times require special handling
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