A meeting-room bot ingested every hold on the Tuesday calendar. Two teams booked overlapping hours; Facilities asked for the fewest holds to cancel so the rest never share the room. Product enumerated subsets. Nine holds is 512 masks. A week’s optional slots is not a spreadsheet. Gluing overlaps into one busy bar would be Merge Intervals — occupancy, not cancellations.

Non-overlapping Intervals asks for the fewest ranges to remove. An array of pairs is the input. That count is n minus a maximum non-overlapping keep. The keep is Interval Scheduling: earliest finish, throw the rest away.

This is an interview writeup, not a scheduling lecture. The tutorial owns the proof. Here we only count cuts — originals that survive, not glued bars.

The problem

Given an int[][] intervals where intervals[i] = [start_i, end_i], return the fewest intervals you must remove so the remaining ranges are pairwise non-overlapping. Closed integers that only touch at an endpoint do not conflict: [1, 2] and [2, 4] may both stay. Empty input is 0.

[[1,3],[2,5],[6,8]]     →  1     keep [1,3] and [6,8]; cut the middle
[[1,2],[2,4],[5,7]]     →  0     a shared endpoint is not a conflict
[[1,10],[2,3],[4,6]]    →  1     keep the two shorts; cut the long
[]                      →  0

Note: Two closed ranges conflict when they share an interior point — a[0] < b[1] && b[0] < a[1]. Merge Intervals treats a shared endpoint as occupancy to swallow (next[0] <= current[1]). That is the other job. Do not merge [1, 3] and [2, 5] into [1, 5] and claim you cancelled nothing.

Every compatible subset is the honest brute force

For each of the 2^n masks, test pairwise non-overlap, keep the largest legal set, return n minus that size. Correct. Exponential.

boolean compatible(int[][] intervals, int mask) {
    for (int i = 0; i < intervals.length; i++) {
        if ((mask & (1 << i)) == 0) {
            continue;
        }
        for (int j = i + 1; j < intervals.length; j++) {
            if ((mask & (1 << j)) == 0) {
                continue;
            }
            int[] a = intervals[i];
            int[] b = intervals[j];
            if (a[0] < b[1] && b[0] < a[1]) {
                return false;
            }
        }
    }
    return true;
}

int eraseOverlapBrute(int[][] intervals) {
    int n = intervals.length;
    int bestKeep = 0;
    int subsets = 1 << n;
    for (int mask = 0; mask < subsets; mask++) {
        if (compatible(intervals, mask)) {
            bestKeep = Math.max(bestKeep, Integer.bitCount(mask));
        }
    }
    return n - bestKeep;
}

At nine holds this is a rounding error. At a week’s calendar you paid every subset for a question one sort plus a linear yes/no answers: how many originals survive if each keep finishes first?

Sort by end, keep if it fits, count the cuts

Sort by end. Scan left to right. Keep the first. Keep the next only when start >= lastEnd, then advance lastEnd. Everything else is a cut. Return n - kept.

You never extend an end with max. You never glue two holds into one longer bar. The objects you keep are originals.

[[1,10],[2,3],[4,6]]
sorted by end:  [2,3]  [4,6]  [1,10]

keep [2,3]    lastEnd=3
[4,6]  4>=3   keep     lastEnd=6
[1,10] 1>=6   skip
removals = 3 - 2 = 1

If you had sorted by start, [1, 10] would sit first and both shorts would die — two cuts, worse. Earliest start is the wrong greedy; the tutorial already showed why.

The Java is that walk:

int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) {
        return 0;
    }
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
    int kept = 1;
    int lastEnd = intervals[0][1];
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= lastEnd) {
            kept++;
            lastEnd = intervals[i][1];
        }
    }
    return intervals.length - kept;
}

Time is O(n log n) from the sort, then a linear scan. Extra space is O(1) beyond whatever the sort uses — the answer is a count, not a subset list. Arrays.sort permutes the input array; copy first if the caller still needs filing order.

Note: Sort by end, not start — and do not merge. A long early range is the one the greedy must be free to throw away. Merge keeps every occupied instant; this prompt pays to delete rows.

What interviewers usually poke next

  • Return the kept ranges, not the cut count. Same sort, same predicate; collect instead of kept++. That is the scheduling tutorial’s output. This prompt only wants n - kept.
  • Touching vs nested vs chain. [1,2]+[2,4], [1,10]+[2,3], [1,5]+[4,8] — walk the >= lastEnd test out loud. Touching stays; nested and partial overlap cut one.
  • Weighted holds. A board session worth more than two standups is weighted interval scheduling (DP). Earliest finish is silent on value.
  • Minimum rooms so nobody is cut. Different greedy: how many resources so every range stays. One room plus cancellations is this problem.

You are done with this problem when you can say, out loud, why every subset is correct, why sorting by end makes a linear keep/skip sufficient, and why merging overlaps answers a different question.