Bird
Raised Fist0
Interview PrepintervalsmediumAmazonGoogleFacebookBloomberg

Non-overlapping Intervals (Max Non-Overlap)

Choose your preparation mode4 modes available
📋
Problem

Imagine you are organizing a conference with multiple talks, and you want to schedule as many talks as possible without any overlaps in their time slots.

Given an array of intervals where intervals[i] = [start_i, end_i], find the maximum number of intervals you can select such that no two intervals overlap. Return the maximum count of such non-overlapping intervals.

1 ≤ n ≤ 10^50 ≤ start_i < end_i ≤ 10^9
Edge cases: All intervals overlap completely → output 1Intervals are already non-overlapping → output nIntervals with same start and end times → output 1
</>
IDE
def max_non_overlapping_intervals(intervals: list[list[int]]) -> int:public int maxNonOverlappingIntervals(int[][] intervals)int maxNonOverlappingIntervals(vector<vector<int>>& intervals)function maxNonOverlappingIntervals(intervals)
def max_non_overlapping_intervals(intervals):
    # Write your solution here
    pass
class Solution {
    public int maxNonOverlappingIntervals(int[][] intervals) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int maxNonOverlappingIntervals(vector<vector<int>>& intervals) {
    // Write your solution here
    return 0;
}
function maxNonOverlappingIntervals(intervals) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: 1Sorting intervals by start time instead of end time causes greedy to pick fewer intervals.✅ Sort intervals by their end time before selecting intervals greedily.
Wrong: 0Not handling empty input or single interval input correctly, returning default zero or uninitialized value.✅ Add base case checks: return 0 if intervals empty, return 1 if single interval.
Wrong: 2Off-by-one error in overlap check, treating intervals touching at boundaries as overlapping.✅ Change overlap condition to allow intervals where start == last selected end.
Wrong: 4Allowing reuse of intervals multiple times (unbounded selection) instead of 0/1 selection.✅ Ensure each interval is selected at most once in greedy iteration.
Wrong: TLEUsing brute force or exponential time approach instead of efficient greedy.✅ Implement sorting by end time and greedy selection for O(n log n) complexity.
✓
Test Cases
t1_01basic
Input{"intervals":[[1,3],[2,4],[3,5]]}
Expected2

We can select intervals [1,3] and [3,5] which do not overlap.

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

Select intervals [1,2], [2,3], and [3,4] which are non-overlapping.

t2_01edge
Input{"intervals":[]}
Expected0

Empty input means no intervals to select, so result is 0.

t2_02edge
Input{"intervals":[[5,10]]}
Expected1

Single interval can always be selected, so result is 1.

t2_03edge
Input{"intervals":[[1,5],[1,5],[1,5]]}
Expected1

All intervals overlap completely, so only one can be selected.

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

Greedy by earliest start fails; correct is to pick [2,3] and [3,5].

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

Must not confuse 0/1 selection with unbounded; each interval can be chosen at most once.

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

Off-by-one errors in overlap check cause wrong count; intervals touching at boundaries are non-overlapping.

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

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

Practice

(1/5)
1. You are given a list of non-overlapping intervals sorted by their start times, and a new interval to insert. Which approach guarantees an optimal solution that correctly merges overlapping intervals after insertion?
easy
A. Use a greedy approach that inserts the new interval at the end and merges overlapping intervals in one pass without sorting.
B. Iterate through intervals and insert the new interval in the correct position without sorting, then merge overlapping intervals.
C. Use dynamic programming to find the minimal set of merged intervals after insertion.
D. Append the new interval, sort all intervals by start time, then merge overlapping intervals in one pass.

Solution

  1. Step 1: Understand the problem constraints

    The intervals are sorted and non-overlapping initially, but inserting a new interval may cause overlaps.
  2. Step 2: Identify the approach that guarantees correct merging

    Appending and then sorting ensures the new interval is placed correctly relative to others, allowing a single pass merge to handle all overlaps reliably.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Sorting after insertion ensures correct order for merging [OK]
Hint: Sort after insertion to guarantee correct merge order [OK]
Common Mistakes:
  • Assuming intervals remain sorted after insertion without sorting
  • Trying to merge without sorting leads to missed overlaps
  • Using DP unnecessarily complicates the problem
2. What is the time complexity of the optimal algorithm that determines if a person can attend all meetings given n intervals, where the algorithm sorts intervals by start time and then checks for overlaps in a single pass?
medium
A. O(n) because we only scan the intervals once after sorting
B. O(n^2) because each interval is compared with all others for overlaps
C. O(n log n) due to sorting the intervals by start time
D. O(log n) because sorting can be done in logarithmic time

Solution

  1. Step 1: Identify sorting cost

    Sorting n intervals by start time takes O(n log n) time.
  2. Step 2: Identify overlap check cost

    Single pass to check overlaps is O(n), which is dominated by sorting.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sorting dominates total time complexity [OK]
Hint: Sorting dominates complexity -> O(n log n) [OK]
Common Mistakes:
  • Confusing single pass check as O(n log n)
  • Assuming nested loops cause O(n^2) here
3. The following code attempts to find the minimum number of arrows to burst balloons. Identify the bug that causes incorrect arrow count in some cases.
medium
A. Line 6: Shooting arrow at start coordinate instead of end coordinate
B. Line 4: Sorting by end coordinate is incorrect
C. Line 2: Missing check for empty input
D. Line 8: Using start > arrow_pos instead of start >= arrow_pos

Solution

  1. Step 1: Analyze arrow shooting position

    Arrow should be shot at the end coordinate of the first balloon to cover maximum overlaps.
  2. Step 2: Identify impact of shooting at start

    Shooting at start may miss balloons overlapping at the end, causing extra arrows.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Correct arrow position is critical for minimal arrow count [OK]
Hint: Arrow must be at end coordinate, not start [OK]
Common Mistakes:
  • Confusing start and end coordinates for arrow position
  • Using >= instead of > causing overcount
  • Ignoring empty input edge case
4. 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
5. Suppose intervals can be reused multiple times (i.e., you can merge overlapping intervals repeatedly, possibly reusing intervals). Which modification to the merge intervals algorithm correctly handles this scenario?
hard
A. Use the same sorting + one pass merge approach; repeated intervals will be merged naturally.
B. Sort intervals and repeatedly apply the merge pass until no changes occur, which may take multiple passes.
C. Use a brute force nested loop approach to merge intervals until no overlaps remain.
D. Use a graph-based approach to find connected components of overlapping intervals and merge each component.

Solution

  1. Step 1: Understand that reusing intervals means overlaps can form complex connected groups.

    Simple one-pass merge assumes intervals appear once and sorted order suffices.
  2. Step 2: Recognize that overlapping intervals form connected components in a graph.

    Building a graph where intervals are nodes and edges represent overlaps allows merging all connected intervals correctly.
  3. Step 3: Evaluate options.

    Use the same sorting + one pass merge approach; repeated intervals will be merged naturally. fails because one pass merge assumes no reuse. Sort intervals and repeatedly apply the merge pass until no changes occur, which may take multiple passes. is inefficient and may not terminate quickly. Use a brute force nested loop approach to merge intervals until no overlaps remain. is brute force and inefficient. Use a graph-based approach to find connected components of overlapping intervals and merge each component. correctly models the problem and merges all connected intervals.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Graph connected components capture all overlapping intervals including reuse. [OK]
Hint: Model reuse as graph connected components [OK]
Common Mistakes:
  • Assuming one pass merge works with reuse
  • Using repeated merges without termination guarantee
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