DSA-037 · Earliest-finish selection and complementary removals

Non-overlapping Intervals

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 9340 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the minimum number of positive-length half-open intervals to remove so the remaining intervals are pairwise compatible.

intervals is a non-null int[][] with 0–100,000 rows [start,end] of arbitrary signed int coordinates. Both methods throw IllegalArgumentException for a null row, a row of length other than two, or start≥end. Zero-duration intervals are explicitly rejected.
Use half-open [start,end) semantics: an interval ending at t is compatible with one starting at t. Duplicate intervals are separate occurrences and conflict because durations are positive.
Return only the minimum removal count and preserve outer order and row values. The optimized method sorts a cloned outer array, reads shared rows without modifying them, and uses no duration subtraction. Concurrent caller mutation during execution is outside the contract.

Examples

Input: [[1,2],[2,3],[1,3]]
Output: 1
Keep [1,2) and [2,3), removing [1,3).
Input: [[0,3],[3,6],[2,4]]
Output: 1
The two length-three intervals fit together; keeping the shortest interval [2,4) would lose both.

Before you start

Closed versus half-open intervals and compatible endpoints
Sorting with safe comparators and invariant or exchange proofs

Recognize the structure

Minimizing removals is equivalent to maximizing the number kept. Among compatible next choices, an earliest finish leaves at least as much room for all future selections as any later finish.

Try before revealing

Hint 1

Minimize removals by maximizing the kept occurrences.

Hint 2

Which first finish leaves the most room for every later choice?

Hint 3

Sort by end, keep each compatible interval, and subtract kept from n.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Dynamic programming over compatible predecessors

Sort by finish. Let bestEnding[i] be the largest compatible schedule ending with interval i; try every earlier j whose end≤start[i], and set bestEnding[i]=max(1,bestEnding[j]+1). For [0,3),[2,4),[3,6), the states are 1,1,2, so keep two and remove one. This O(n²) baseline explicitly explores all predecessor choices.

Improve the baseline

Change the objective to kept count

With n fixed, removals=n-kept. An optimal maximum-cardinality compatible set therefore solves minimum removals.

Sort by end and take compatible intervals

Scan ascending finish times. Select the first interval, then select a later one exactly when its start≥the last selected end.

Count the discarded occurrences

Every rejected interval conflicts with the last selected interval. Return n minus the total selected; equal-end choices need no special duration or tie heuristic for this count-only API.

Why it is correct

First-choice exchange

Consider any maximum compatible schedule and its earliest interval. The globally earliest-finishing interval ends no later. Replacing that first choice by the greedy one preserves compatibility with all later choices and does not reduce cardinality.

Residual exchange

After selecting an interval ending at e, only intervals starting at or after e remain eligible. Apply the same earliest-finish exchange within that residual set. Induction produces a maximum-cardinality schedule.

Completion and complement

The sorted scan considers all eligible intervals in finish order. A rejected interval begins before the selected end and cannot follow it; the exchange argument shows retaining the chosen earlier finish does not lose an optimum. Subtracting the optimal kept count from n gives the minimum removals, including zero for empty input.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static void validate(int[][] intervals) {
        for (int[] row : intervals) if (row == null || row.length != 2 || row[0] >= row[1]) throw new IllegalArgumentException("positive-length half-open intervals required");
    }
    public static int eraseOverlapIntervals(int[][] intervals) {
        validate(intervals);
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, Comparator.comparingInt(value -> value[1]));
        int kept = 0, end = 0;
        for (int[] next : sorted) {
            if (kept == 0 || next[0] >= end) {
                kept++;
                end = next[1];
            }
        }
        return sorted.length - kept;
    }
    public static int baseline(int[][] intervals) {
        validate(intervals);
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, Comparator.comparingInt(value -> value[1]));
        int[] bestEnding = new int[sorted.length];
        int maximum = 0;
        for (int i = 0; i < sorted.length; i++) {
            bestEnding[i] = 1;
            for (int j = 0; j < i; j++) if (sorted[j][1] <= sorted[i][0]) bestEnding[i] = Math.max(bestEnding[i], bestEnding[j] + 1);
            maximum = Math.max(maximum, bestEnding[i]);
        }
        return sorted.length - maximum;
    }
}

Read the meaningful blocks

Safe end comparator

Comparator.comparingInt avoids subtraction overflow for Integer.MIN_VALUE and Integer.MAX_VALUE endpoints.

Guard the first selection explicitly

kept==0 handles all signed starting coordinates; zero is only an initial local value, not a fake previously selected boundary.

Clone the outer order

Sorting only a clone preserves the caller’s order. Rows are shared read-only, so a deep copy is unnecessary for this scalar result.

Complexity

O(n log n) time for validation, sorting, and one scan. O(n) auxiliary storage for the cloned row-reference array and object-sort workspace; no selected-set output is allocated.

The predecessor-DP baseline costs O(n²) time after sorting and O(n) state. Both operate on interval occurrences; identical coordinates do not collapse into one input item.

Exact-state walkthroughs

Reveal normal and boundary traces

Earliest finish defeats shortest duration

Input: [[0,3],[3,6],[2,4]] · Result: 1

Step 1 of 5: Sort a copied outer order by finish time.

No interval has been selected; rows are observed without mutation.

Half-open meeting coordinates — end excluded

Endpoint spacing is compressed to show coordinate order; bar lengths do not measure duration. Filled dots include an endpoint; an open right circle excludes it. Dashed vertical lines are fixed arrow positions.

Row #0: [0, 3)
Row #1: [2, 4)
Row #2: [3, 6)

Chosen half-open occurrences — decision history

Empty at this step.

The Java count-only method retains the kept count and last finish; the selected list is explanatory history.

State after this step
Variable	Value
intervalRows	`[[0,3],[2,4],[3,6]]`
index	`-1`
lastEnd	`null`
keptIntervals	`[]`
keptCount	`0`
removedCount	`0`
closed	`false`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int[][] intervals) {
 4         for (int[] row : intervals) if (row == null || row.length != 2 || row[0] >= row[1]) throw new IllegalArgumentException("positive-length half-open intervals required");
 5     }
 6     public static int eraseOverlapIntervals(int[][] intervals) {
 7         validate(intervals);
 8         int[][] sorted = intervals.clone();
 9         Arrays.sort(sorted, Comparator.comparingInt(value -> value[1]));
10         int kept = 0, end = 0;
11         for (int[] next : sorted) {
12             if (kept == 0 || next[0] >= end) {
13                 kept++;
14                 end = next[1];
15             }
16         }
17         return sorted.length - kept;
18     }
19     public static int baseline(int[][] intervals) {
20         validate(intervals);
21         int[][] sorted = intervals.clone();
22         Arrays.sort(sorted, Comparator.comparingInt(value -> value[1]));
23         int[] bestEnding = new int[sorted.length];
24         int maximum = 0;
25         for (int i = 0; i < sorted.length; i++) {
26             bestEnding[i] = 1;
27             for (int j = 0; j < i; j++) if (sorted[j][1] <= sorted[i][0]) bestEnding[i] = Math.max(bestEnding[i], bestEnding[j] + 1);
28             maximum = Math.max(maximum, bestEnding[i]);
29         }
30         return sorted.length - maximum;
31     }
32 }
33

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Sort a copied outer order by finish time.
No interval has been selected; rows are observed without mutation.
intervalRows
[[0,3],[2,4],[3,6]]
index
-1
lastEnd
null
keptIntervals
[]
keptCount
0
removedCount
0
closed
false
Keep this earliest-finishing compatible occurrence.
Chosen occurrences form a compatible chain. The trace lists its history; Java retains only the count and last end.
intervalRows
[[0,3],[2,4],[3,6]]
index
0
lastEnd
3
taken
true
keptIntervals
[[0,3]]
keptCount
1
removedCount
0
closed
false
Discard this conflicting occurrence.
Chosen occurrences form a compatible chain. The trace lists its history; Java retains only the count and last end.
intervalRows
[[0,3],[2,4],[3,6]]
index
1
lastEnd
3
taken
false
keptIntervals
[[0,3]]
keptCount
1
removedCount
1
closed
false
Keep this earliest-finishing compatible occurrence.
Chosen occurrences form a compatible chain. The trace lists its history; Java retains only the count and last end.
intervalRows
[[0,3],[2,4],[3,6]]
index
2
lastEnd
6
taken
true
keptIntervals
[[0,3],[3,6]]
keptCount
2
removedCount
1
closed
false
Return the contract result.
The result satisfies the stated objective, endpoint policy, and input-preservation contract.
result
1

Duplicate occurrences and touching compatibility

Input: [[1,2],[1,2],[2,3]] · Result: 1

Step 1 of 5: Sort a copied outer order by finish time.

No interval has been selected; rows are observed without mutation.

Half-open meeting coordinates — end excluded

Row #0: [1, 2)
Row #1: [1, 2)
Row #2: [2, 3)

Chosen half-open occurrences — decision history

Empty at this step.

The Java count-only method retains the kept count and last finish; the selected list is explanatory history.

State after this step
Variable	Value
intervalRows	`[[1,2],[1,2],[2,3]]`
index	`-1`
lastEnd	`null`
keptIntervals	`[]`
keptCount	`0`
removedCount	`0`
closed	`false`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static void validate(int[][] intervals) {
 4         for (int[] row : intervals) if (row == null || row.length != 2 || row[0] >= row[1]) throw new IllegalArgumentException("positive-length half-open intervals required");
 5     }
 6     public static int eraseOverlapIntervals(int[][] intervals) {
 7         validate(intervals);
 8         int[][] sorted = intervals.clone();
 9         Arrays.sort(sorted, Comparator.comparingInt(value -> value[1]));
10         int kept = 0, end = 0;
11         for (int[] next : sorted) {
12             if (kept == 0 || next[0] >= end) {
13                 kept++;
14                 end = next[1];
15             }
16         }
17         return sorted.length - kept;
18     }
19     public static int baseline(int[][] intervals) {
20         validate(intervals);
21         int[][] sorted = intervals.clone();
22         Arrays.sort(sorted, Comparator.comparingInt(value -> value[1]));
23         int[] bestEnding = new int[sorted.length];
24         int maximum = 0;
25         for (int i = 0; i < sorted.length; i++) {
26             bestEnding[i] = 1;
27             for (int j = 0; j < i; j++) if (sorted[j][1] <= sorted[i][0]) bestEnding[i] = Math.max(bestEnding[i], bestEnding[j] + 1);
28             maximum = Math.max(maximum, bestEnding[i]);
29         }
30         return sorted.length - maximum;
31     }
32 }
33

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Sort a copied outer order by finish time.
No interval has been selected; rows are observed without mutation.
intervalRows
[[1,2],[1,2],[2,3]]
index
-1
lastEnd
null
keptIntervals
[]
keptCount
0
removedCount
0
closed
false
Keep this earliest-finishing compatible occurrence.
Chosen occurrences form a compatible chain. The trace lists its history; Java retains only the count and last end.
intervalRows
[[1,2],[1,2],[2,3]]
index
0
lastEnd
2
taken
true
keptIntervals
[[1,2]]
keptCount
1
removedCount
0
closed
false
Discard this conflicting occurrence.
Chosen occurrences form a compatible chain. The trace lists its history; Java retains only the count and last end.
intervalRows
[[1,2],[1,2],[2,3]]
index
1
lastEnd
2
taken
false
keptIntervals
[[1,2]]
keptCount
1
removedCount
1
closed
false
Keep this earliest-finishing compatible occurrence.
Chosen occurrences form a compatible chain. The trace lists its history; Java retains only the count and last end.
intervalRows
[[1,2],[1,2],[2,3]]
index
2
lastEnd
3
taken
true
keptIntervals
[[1,2],[2,3]]
keptCount
2
removedCount
1
closed
false
Return the contract result.
The result satisfies the stated objective, endpoint policy, and input-preservation contract.
result
1

Test the contract

Input: []
Output: 0
No removals needed.
Input: [[1,2],[1,2],[1,2]]
Output: 2
Duplicates are separate conflicting occurrences.
Input: [[1,2],[2,3]]
Output: 0
Touching endpoints are compatible.
Input: [[4,4]]
Output: IllegalArgumentException
Zero duration is rejected.

Common mistakes and counterexamples

Choose shortest duration

Counterexample: [0,3),[3,6),[2,4) lets two long intervals fit, but choosing the length-two middle interval keeps only one.

Compare finish times rather than durations.

Choose earliest start

Counterexample: [0,100),[1,2),[2,3) would keep only the long first interval.

Choose earliest compatible finish.

Treat touching as overlap

Counterexample: [1,2) and [2,3) need no removal.

Accept start≥lastEnd under half-open semantics.

Follow-ups

Return a selected set.

Carry original indices with sorted rows and record each selected occurrence. Define deterministic tie order if the witness identity matters; any optimal kept set suffices for the current scalar contract.

Assign weights or profits.

Earliest finish maximizes count, not weight. Weighted interval scheduling uses predecessor lookup and DP, comparing skip versus take+best compatible prefix.

Allow zero-duration intervals.

First specify whether a zero-length half-open interval occupies no resource and is compatible with everything. The current API rejects it; blindly sorting such intervals can change pairwise conflict reasoning and tie behavior.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 145/20,000 characters

Self-review

I can perform the earliest-finish exchange.I distinguish unweighted count from weighted scheduling.I preserve input order and use safe comparisons.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-16 · Original teaching content, examples, and Java implementations authored for AceYourInterviews. These standard algorithmic tasks carry no company-frequency or interview-outcome claims.