How should I practice Minimum Removals for Non-Overlapping Intervals?

Start by reading the full statement, solve the visible examples, then compare the pattern against related ByteDance phone screen problems in FastPrep.

Is Minimum Removals for Non-Overlapping Intervals associated with ByteDance?

FastPrep tags this as a ByteDance phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Minimum Removals for Non-Overlapping Intervals

Learn this problem

● Medium

ByteDanceFULLTIMEPHONE SCREEN

Problem statement

You are given a collection of integer intervals intervals, where each interval is represented as [start, end].

Remove the minimum number of intervals so that every pair of remaining intervals is non-overlapping. When one interval ends exactly where another begins, they are compatible and may both remain.

Return the minimum number of intervals that must be removed.

Function

minimumIntervalRemovals(intervals: int[][]) → int

Examples

Example 1

intervals = [[1,2],[2,3],[3,4],[1,3]]return = 1

Removing [1,3] leaves three pairwise non-overlapping intervals. The intervals [1,2] and [2,3] may both remain because endpoint contact is allowed.

Example 2

intervals = [[1,2],[1,2],[1,2]]return = 2

At most one of the three identical intervals can remain, so two removals are necessary.

Example 3

intervals = [[-5,-2],[-2,0],[0,1]]return = 0

Every neighboring pair only touches at an endpoint, so all three intervals may remain.

Constraints

0 <= intervals.length <= 100000.
Every interval has exactly two signed 32-bit integer endpoints [start, end] with start < end.