DSA · Intervals · #128
Non-overlapping Intervals
Module 67 · difficulty 3/5·⏱ 30:00starts on first keystroke
Given an array `intervals` where `intervals[i] = [startᵢ, endᵢ]`, return the **minimum number of intervals you need to remove** to make the rest of the intervals non-overlapping. Intervals that touch at a single point (e.g. `[1, 2]` and `[2, 3]`) are **not** considered overlapping. Implement the function `eraseOverlapIntervals(intervals)` which returns an integer.
Examples
intervals = [[1,2],[2,3],[3,4],[1,3]]→1— Removing [1,3] leaves [[1,2],[2,3],[3,4]], which are non-overlapping.intervals = [[1,2],[1,2],[1,2]]→2— Two of the identical intervals must be removed.intervals = [[1,2],[2,3]]→0— They only touch at point 2, so nothing needs removing.
Constraints
- · 1 <= intervals.length <= 10^5
- · intervals[i].length == 2
- · -5 * 10^4 <= startᵢ < endᵢ <= 5 * 10^4
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.