Non-overlapping Intervals

MediumIntervalsgreedy interval

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a list of intervals, where each intervals[i] = [start_i, end_i] represents a half-open interval [start_i, end_i). Your task is to remove the **minimum** number of intervals so that the remaining intervals are pairwise **non-overlapping**. Return that minimum count. Two intervals are considered non-overlapping if they touch only at an endpoint. For example, [1, 2] and [2, 3] do **not** overlap, since the first ends exactly where the second begins. In contrast, [1, 3] and [2, 4] overlap because they share the open span (2, 3). If the input already contains no overlapping intervals, the answer is 0.

Examples

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Removing `[1,3]` leaves `[[1,2],[2,3],[3,4]]`, which are all non-overlapping. One removal is enough.
Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
The three intervals are identical and all overlap each other. Keep one and remove the other two.
Input: intervals = [[1,2],[2,3]]
Output: 0
These intervals only touch at the point `2`, so they are already non-overlapping and nothing needs to be removed.

Constraints

  • `1 <= intervals.length <= 10^5`
  • `intervals[i].length == 2`
  • `-5 * 10^4 <= start_i < end_i <= 5 * 10^4`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More greedy interval problems