Non-overlapping Intervals (Max Non-Overlap)

📋

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
}

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

Focus on handling empty and minimal inputs correctly before tackling edge cases.

Review greedy algorithm correctness and common pitfalls like sorting criteria.

Ensure your solution is efficient enough to handle large inputs within time limits.

t1_01basic

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

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Try sorting intervals by their end times to maximize non-overlapping selections.

💡 Use a greedy approach: always pick the interval with the earliest end time that doesn't overlap.

💡 Iterate intervals sorted by end; select if start >= last selected end.

Why it failed: Incorrect output likely due to not sorting by end time or incorrect overlap check. Fix by sorting intervals by end and selecting intervals greedily.

✓ Correctly implements greedy selection after sorting by end time.

t1_02basic

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Check if intervals can be chained by end time to start time equality.

💡 Remember intervals that end exactly when another starts do not overlap.

💡 Sort by end time and pick intervals where start >= last selected end.

Why it failed: Output less than 3 indicates failure to handle intervals touching at boundaries correctly. Fix by allowing start == last selected end as non-overlapping.

✓ Correctly handles intervals that touch but do not overlap.

t2_01edge

Input{"intervals":[]}

Expected0

⏱ Performance - must finish in 2000ms

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

💡 Consider what happens when there are no intervals.

💡 The maximum count of non-overlapping intervals in empty input is zero.

💡 Return 0 immediately if intervals list is empty.

Why it failed: Returning non-zero for empty input indicates missing base case. Fix by checking if intervals is empty and return 0.

✓ Correctly returns 0 for empty input.

t2_02edge

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

Expected1

⏱ Performance - must finish in 2000ms

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

💡 Check behavior when only one interval is present.

💡 Single interval means maximum non-overlapping count is 1.

💡 Return 1 if intervals length is 1.

Why it failed: Returning 0 or more than 1 for single interval input indicates incorrect base case handling. Fix by returning 1 when intervals length is 1.

✓ Correctly returns 1 for single interval input.

t2_03edge

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

Expected1

⏱ Performance - must finish in 2000ms

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

💡 Consider intervals with identical start and end times.

💡 Only one interval can be chosen if all overlap fully.

💡 Ensure algorithm picks only one interval in such cases.

Why it failed: Output greater than 1 means algorithm fails to detect full overlap. Fix by sorting by end and selecting first interval only.

✓ Correctly handles fully overlapping identical intervals.

t3_01corner

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

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Beware of greedy by earliest start time; it can fail.

💡 Sort intervals by end time to avoid greedy trap.

💡 Pick intervals with earliest end time to maximize count.

Why it failed: Output 1 indicates greedy by start time mistake. Fix by sorting intervals by end time instead of start time.

✓ Correctly avoids greedy start-time trap by sorting by end time.

t3_02corner

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Remember intervals are 0/1 choices, not unbounded.

💡 Do not reuse intervals multiple times.

💡 Select intervals greedily without overlap, each once.

Why it failed: Output greater than 3 indicates unbounded reuse of intervals. Fix by ensuring each interval is selected at most once.

✓ Correctly enforces 0/1 selection constraint.

t3_03corner

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

Expected3

⏱ Performance - must finish in 2000ms

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

💡 Check if your overlap condition uses strict inequality.

💡 Intervals where start == last selected end do not overlap.

💡 Use start >= last_end to allow touching intervals.

Why it failed: Output 2 indicates off-by-one overlap check error. Fix by changing overlap condition to start >= last selected end.

✓ Correctly handles intervals touching at boundaries.

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) solution to complete within 2 seconds.

💡 Brute force O(2^n) will time out; use sorting + greedy O(n log n).

💡 Sort intervals by end time before selection.

💡 Iterate once to select non-overlapping intervals greedily.

Why it failed: TLE indicates use of brute force or inefficient approach. Fix by implementing O(n log n) greedy algorithm sorting by end time.

✓ Algorithm runs in O(n log n) time and passes performance test.

Practice

1. You are given a list of trips, each with a number of passengers, a start location, and an end location. You need to determine if a vehicle with a fixed capacity can carry all passengers without exceeding capacity at any point along the route. Which algorithmic approach best guarantees an optimal and efficient solution?

easy

A. Brute force simulation by incrementing passenger count at every location for each trip

B. Greedy algorithm that picks trips with earliest end location first

C. Dynamic programming to find maximum passengers at each location using state transitions

D. Sweep line algorithm that processes passenger count changes at trip start and end points

Solution

1. Step 1: Understand problem constraints

   The problem requires tracking passenger counts over intervals defined by start and end locations.

2. Step 2: Identify suitable algorithm

   Sweep line processes events (passenger changes) in sorted order, efficiently tracking capacity usage without simulating every location.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sweep line handles interval events optimally [OK]

Hint: Intervals with start/end events -> sweep line [OK]

Common Mistakes:

• Assuming greedy earliest end works for capacity constraints
• Thinking DP is needed for counting passengers
• Using brute force for large location ranges

2. You are given a list of intervals and a list of points. For each point, you need to find how many intervals contain it. Which algorithmic approach guarantees an optimal solution with time complexity better than O(n*m), where n is the number of intervals and m is the number of points?

easy

A. Use a line sweep algorithm by sorting interval start and end events along with points, then sweeping through them.

B. Use a brute force nested loop checking each point against every interval.

C. Use dynamic programming to precompute counts for all points in the range.

D. Sort intervals and points, then for each point use binary search to count intervals starting before and ending after the point.

Solution

1. Step 1: Understand brute force and binary search limitations

   Brute force is O(n*m), too slow for large inputs. Binary search approach requires careful handling of interval ends and starts but is less optimal than line sweep.

2. Step 2: Recognize line sweep advantages

   Line sweep sorts all events (starts, points, ends) and processes them in one pass, maintaining active intervals count efficiently in O((n+m) log (n+m)) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Line sweep processes all events sorted by coordinate with correct event ordering [OK]

Hint: Line sweep processes starts, points, ends in sorted order [OK]

Common Mistakes:

• Assuming binary search alone is optimal
• Thinking DP applies here
• Using brute force for large inputs

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. 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. 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