Crack the Backend

Problem Statement

Given an array of intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove so that the remaining intervals are non-overlapping. Two intervals overlap if they share any point (e.g. [1,2] and [2,3] overlap at 2).

Key Observations

Sort by end time: If we sort by end, we can greedily keep an interval if its start >= lastEnd (where lastEnd is the end of the last kept interval). Otherwise we "remove" it (don't update lastEnd). The idea: among overlapping intervals, we keep the one that ends earliest so we leave more room for future intervals. So we iterate in order of end; if the current interval does not overlap the last kept one (current.start >= lastEnd), we keep it and set lastEnd = current.end; else we skip it (count as removed).

Approach

High-level: Sort by interval end. lastEnd = -inf, remove = 0. For each [s,e]: if s >= lastEnd then lastEnd = e (keep); else remove++. Return remove.

Steps: Arrays.sort(intervals, (a,b)->a[1]-b[1]). int lastEnd = Integer.MIN_VALUE, remove = 0. For each: if interval[0] >= lastEnd then lastEnd = interval[1]; else remove++. Return remove.

Implementation

Java

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, (a,b) -> a[1]-b[1]);
    int lastEnd = Integer.MIN_VALUE, remove = 0;

    for (int[] i : intervals) {
        if (i[0] >= lastEnd) {
            lastEnd = i[1];
        }
        else {
            remove++;
        }
    }

    return remove;
}

Test Cases

Example 1

Input

intervals = [[1,2],[2,3],[3,4],[1,3]]

Expected

1

Explanation

Remove [1,3].

Complexity Analysis

Time: typically O(n) or O(n log n).
Space: O(1) or O(n).

Follow-ups

Prove greedy choice property; handle ties.