Non-overlapping Intervals

Return the minimum number of intervals you need to remove so the rest don't overlap.

A way to picture it

You have one meeting room and too many bookings. The winning strategy is almost lazy: always keep the meeting that finishes earliest. It frees the room soonest, leaving the most space for everyone else.

How to approach it

Sort by end time. Keep an interval if it starts at or after the last kept end; otherwise remove it.

Example

Input: {"intervals":[[1,2],[2,3],[3,4],[1,3]]}. Output: 1.

Complexity: O(n log n) time and O(1) extra space. Sorting, then one greedy pass.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.