Interval Scheduling

Many problems involve intervals (start, end). Classic greedy strategies: sort by end time to maximize the number of non-overlapping intervals, or sort by start time to merge overlapping ones.

Maximum Non-Overlapping Intervals

Problem: Choose as many intervals as possible so that no two overlap.

Greedy: Sort intervals by end time. Iterate; take an interval if its start is not before the last chosen interval’s end. This maximizes count.

JavaCopy
public int maxNonOverlapping(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    int count = 0, lastEnd = Integer.MIN_VALUE;
    for (int[] i : intervals) {
        if (i[0] >= lastEnd) {
            count++;
            lastEnd = i[1];
        }
    }
    return count;
}

Merge Overlapping Intervals

Problem: Merge all overlapping intervals.

Greedy: Sort by start time. Walk through; if the current interval overlaps the last one in the result, merge (extend the end); otherwise append a new interval.

JavaCopy
public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    for (int[] i : intervals) {
        if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < i[0])
            merged.add(i.clone());
        else
            merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], i[1]);
    }
    return merged.toArray(int[][]::new);
}

Summary

• Max non-overlapping: sort by end, take if start ≥ last end.
• Merge overlapping: sort by start, merge if current overlaps last in result. Both run in O(n log n).