Intervals - Non-overlapping Intervals

Given an array of intervals, find the minimum number of intervals to remove to make the rest non-overlapping.

Input: [[1,2],[2,3],[3,4],[1,3]] → Output: 1

Input: [[1,2],[1,2],[1,2]] → Output: 2

Greedy: sort by end time. Keep the interval with the earliest end time; remove overlapping ones.

Sort by end time.
Greedily keep the first interval (earliest end). Count = 0.
For each next interval: if it starts >= previous end, keep it (update prevEnd).
Otherwise, remove it (count++).

import java.util.*; class Solution { public int eraseOverlapIntervals(int[][] intervals) { Arrays.sort(intervals, (a,b) -> a[1] - b[1]); int prevEnd = intervals[0][1], remove = 0; for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] < prevEnd) remove++; else prevEnd = intervals[i][1]; } return remove; } }

Time Complexity: O(N log N)
Space Complexity: O(1)