Faangprep Logo
Log inStart free
Browse curriculum

Non-overlapping Intervals

Find the minimum number of intervals to remove to eliminate all overlaps.

MediumSolve on LeetCode

Problem Understanding

Each entry of intervals is a pair [start, end]. Return the fewest intervals you have to delete so that none of the remaining ones overlap. Intervals that only touch at an endpoint, like [1,2] and [2,3], do not count as overlapping.

Example 1:

  • Input: [[1,2],[2,3],[3,4],[1,3]]
  • Output: 1
  • Explanation: Remove [1,3] to handle the overlaps with [1,2] and [2,3].

Algorithm Strategy

This is a classic Greedy problem. Removing as few intervals as possible is the same as keeping as many as possible, and the interval that finishes earliest leaves the most room for everything after it.

  1. Sort by End Time: Sort intervals by end ascending.
  2. Keep the first: It ends earliest, so keep it and set prevEnd to its end.
  3. Check each later interval curr:
    • If curr.start >= prevEnd, it does not overlap the last kept interval: keep it and set prevEnd = curr.end.
    • Otherwise it overlaps. Because of the sort, curr ends no earlier than the interval already kept, so keeping that one never leaves less room: remove curr and add 1 to the count.
  4. Return the count.

Interactive Visualization

See how sorting by End Time allows us to reliably pick the 'best' intervals to keep.

Dry Run

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

Step Interval End Time Decision Count
Init - - Sort by End: [[1,2], [2,3], [1,3], [3,4]] 0
1 [1,2] 2 Keep. prevEnd = 2. 0
2 [2,3] 3 Start 2 >= prev 2. Keep. prevEnd = 3. 0
3 [1,3] 3 Start 1 < prev 3. Overlap! Remove. 1
4 [3,4] 4 Start 3 >= prev 3. Keep. prevEnd = 4. 1

Edge Cases & Common Mistakes

  • Equal End Times: The sort order for same end times doesn't affect correctness for count, though sorting by start (secondary) produces consistent selection.
  • Touching Intervals: [1,2] and [2,3] do NOT overlap. Logic must use >=.
  • Negative Numbers: Intervals can have negative coordinates.

Solution

Greedy optimization O(N log N).

Non-overlapping Intervals Code
1var eraseOverlapIntervals = function(intervals) {
2    if (!intervals.length) return 0;
3    intervals.sort((a, b) => a[1] - b[1]);
4    
5    let count = 0;
6    let prevEnd = intervals[0][1];
7    
8    for (let i = 1; i < intervals.length; i++) {
9        if (intervals[i][0] >= prevEnd) {
10            prevEnd = intervals[i][1];
11        } else {
12            count++;
13        }
14    }
15    return count;
16};
Previous

Insert Interval

Next

Meeting Rooms

The approach, step by step

  1. Sort by end

    Sort the intervals by end time and keep the first one.

  2. Keep or remove

    Keep an interval when it starts at or after prevEnd and move prevEnd to its end; otherwise count it as removed.

  3. Return the count

    Return how many intervals were removed.

Frequently asked questions

Why sort by end time for Non-overlapping Intervals?

Keeping the interval that finishes first leaves the most room for the rest. Sorting by end lets one pass keep every interval that fits and remove the others, which removes as few as possible.

Do [1,2] and [2,3] overlap in this problem?

No. An interval is kept when its start is greater than or equal to the last kept end, so intervals that only touch are both kept.

What is the time complexity?

O(n log n) for the sort and O(n) for the pass. Apart from the sort, it uses O(1) extra space.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description