Return the minimum number of intervals you need to remove to make the rest non-overlapping.

Example 1:

• Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
• Output: 1

Constraints:

• 1 <= intervals.length <= 10^5

Greedy scheduling problem: sort by end time, pick interval with earliest end time.

Interval Scheduling / Greedy Choice

graph TD
    Start["Input Data"] --> Process["Process Element by Element"]
    Process --> Lookup{"Hash Map / Set Lookup"}
    Lookup -- "Match Found" --> Return["Return Indices / Result"]
    Lookup -- "No Match" --> Store["Store in Map / Set"]
    Store --> Process

function eraseOverlapIntervals(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let count = 0, prevEnd = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < prevEnd) count++;
    else prevEnd = intervals[i][1];
  }
  return count;
}

• Time Complexity: O(n log n)
• Space Complexity: O(1)
• Explanation: Greedy choice by end time.

function eraseOverlapIntervals(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let count = 0, prevEnd = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < prevEnd) count++;
    else prevEnd = intervals[i][1];
  }
  return count;
}

• Time Complexity: O(n log n)
• Space Complexity: O(1)
• Explanation: Earliest end time greedy sorting.

1. Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
2. Iterate & Evaluate: Process the input according to the boundary conditions.
3. Update & Return: Compute the optimal answer and return early or at termination.

Sorting by end time leaves maximum room for future non-overlapping intervals.

1. Sort intervals by end time.

👉 Solve this problem interactively in the DSA Lab