Greedy / Intermediate

Interval Scheduling (Non-Overlapping) Visualizer

Sort by end time. Keep an interval if it starts at or after the end of the last one kept. Finishing as early as possible leaves the most room for everything after.

Start the Interval Scheduling (Non-Overlapping) simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best time	O(n log n)
Average time	O(n log n)
Worst time	O(n log n)
Extra space	O(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

Sort the 6 intervals by end time. Each row is one interval on the timeline.
1-2: does it start at or after the beginning?
Yes. Keep it. The timeline is now busy until 2.
1-3: does it start at or after the last end 2?
No, it starts at 1, before 2. Remove it.
2-4: does it start at or after the last end 2?
Yes. Keep it. The timeline is now busy until 4.
3-5: does it start at or after the last end 4?
No, it starts at 3, before 4. Remove it.
5-7: does it start at or after the last end 4?
Yes. Keep it. The timeline is now busy until 7.
6-8: does it start at or after the last end 7?
No, it starts at 6, before 7. Remove it.
Kept 3 of 6. Remove 3 to leave no overlaps.

Try it with your own input →

Interval scheduling (non-overlapping) in Java, Python, C++, C and JavaScript

JavaPythonC++CJavaScript

int eraseOverlapIntervals(int[][] iv) {
  Arrays.sort(iv, (a, b) -> a[1] - b[1]);
  int kept = 0, end = Integer.MIN_VALUE;
  for (int[] x : iv) {
    if (x[0] >= end) {
      kept++;
      end = x[1];
    }
  }
  return iv.length - kept;
}

def erase_overlap_intervals(iv):
    iv.sort(key=lambda x: x[1])
    kept, end = 0, float('-inf')
    for x in iv:
        if x[0] >= end:
            kept += 1
            end = x[1]
    return len(iv) - kept

int eraseOverlapIntervals(vector<vector<int>>& iv) {
  sort(iv.begin(), iv.end(), [](const auto& a, const auto& b) { return a[1] < b[1]; });
  int kept = 0, end = INT_MIN;
  for (const auto& x : iv) {
    if (x[0] >= end) {
      kept++;
      end = x[1];
    }
  }
  return iv.size() - kept;
}

#include <limits.h>
#include <stdlib.h>

int byEnd(const void* a, const void* b) { return ((const int*)a)[1] - ((const int*)b)[1]; }

int eraseOverlapIntervals(int iv[][2], int n) {
  qsort(iv, n, sizeof iv[0], byEnd);
  int kept = 0, end = INT_MIN;
  for (int i = 0; i < n; i++) {
    if (iv[i][0] >= end) {
      kept++;
      end = iv[i][1];
    }
  }
  return n - kept;
}

function eraseOverlapIntervals(iv) {
  iv.sort((a, b) => a[1] - b[1]);
  let kept = 0, end = -Infinity;
  for (const x of iv) {
    if (x[0] >= end) {
      kept++;
      end = x[1];
    }
  }
  return iv.length - kept;
}

In an interview

LeetCode 435, Non-overlapping Intervals: remove the fewest intervals so the rest do not overlap. Same idea: 452 Minimum Arrows to Burst Balloons, and meeting-room booking.

Sorting by start time or by length is the classic wrong answer. Ask the interviewer whether touching ends (3-5 and 5-7) count as overlapping; here they do not.

More greedy

Jump Game visualizer