Quick Overview

Find the minimum number of intervals to remove so the remaining set has no overlaps, while allowing intervals to touch at endpoints. The problem covers duplicate intervals, negative coordinates, stable overlap semantics, and large-input complexity.

Remove the Fewest Overlapping Intervals

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

# Remove the Fewest Overlapping Intervals You are given an array of intervals `intervals`, where each interval is `[start, end]` with `start < end`. Return the minimum number of intervals that must be removed so that all remaining intervals are pairwise non-overlapping. Intervals that only touch at an endpoint do not overlap. For example, `[1, 2]` and `[2, 4]` may both remain. Implement `minIntervalsToRemove(intervals)`. ## Constraints - `1 <= intervals.length <= 200,000` - `-10^9 <= start < end <= 10^9` - Duplicate intervals are allowed and occupy separate positions. - Return one integer. ## Example 1 ```text Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]] Output: 1 ``` Removing `[1, 3]` leaves three intervals that touch only at endpoints. ## Example 2 ```text Input: intervals = [[1, 2], [1, 2], [1, 2]] Output: 2 ``` Only one of the three identical intervals can remain.

Overview: Find the minimum number of intervals to remove so the remaining set has no overlaps, while allowing intervals to touch at endpoints. The problem covers duplicate intervals, negative coordinates, stable overlap semantics, and large-input complexity.

Read the full TikTok Software Engineer interview experience this question came from

Implement minIntervalsToRemove(intervals). Each interval is [start, end] with start < end. Return the minimum number of interval positions to remove so every remaining pair is non-overlapping. Intervals that meet only at an endpoint may both remain. Duplicate intervals are separate positions.

Constraints

  • 1 <= intervals.length <= 200,000
  • Every interval has exactly two integer endpoints [start, end] with start < end.
  • -10^9 <= start < end <= 10^9
  • Duplicate intervals are allowed and occupy separate positions.
  • Intervals whose end and start are equal do not overlap.
  • Return one integer.

Examples

Input: ([[1, 2]],)

Expected Output: 0

Explanation: A single interval already forms a non-overlapping set.

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

Expected Output: 1

Explanation: The first source example removes the longer interval while retaining three endpoint-touching intervals.

Hints

  1. Minimizing removals is the same as maximizing how many intervals remain.
  2. Among intervals available to keep next, consider which ending time leaves the most room.

Loading coding console...

Show the approach

Approach

Maximizing the number kept is equivalent to minimizing removals. Sort intervals by ascending end time and greedily retain an interval whenever its start is at least the end of the most recently retained interval. Choosing the available interval that ends first leaves at least as much room for every later choice as any alternative, so an exchange argument preserves an optimal solution after each selection. Subtract the maximum kept count from the original length.

Time complexity:
O(n log n) for sorting n intervals; the greedy scan is O(n).
Space complexity:
O(n) for a sorted copy of the intervals, excluding sort implementation overhead.