PPractick

The problem

A conference has more talk proposals than one stage can host, and two talks conflict if their time ranges overlap. Talks that merely touch, where one ends exactly when the next starts, are fine. What's the minimum number of talks to cancel so the rest don't overlap? That's n minus the maximum number of compatible talks, and the maximum comes from the classic activity-selection greedy: sort by end time and keep every talk that starts at or after the last kept talk ends.

Example: [[1,2], [2,3], [3,4], [1,3]] → 1 (remove [1,3]).

Function signature

int eraseOverlapIntervals(vector<vector<int>> intervals);

Test cases

Input	Output	Explanation
[[1,2],[2,3],[3,4],[1,3]]	1	Remove [1,3]
[[1,2],[1,2],[1,2]]	2	Keep one copy
[[1,2],[2,3]]	0	Touching is allowed
[[1,100],[11,22],[1,11],[2,12]]	2	Keep [1,11] and [11,22]
[[0,2],[1,3],[2,4],[3,5],[4,6]]	2	Keep [0,2], [2,4], [4,6]

(Confirm: [a,b] and [b,c] don't overlap; the answer is a count of removals.)

How interviewers phrase it

• "Given an array of intervals, return the minimum number of intervals you need to remove to make the rest non-overlapping" (LeetCode 435).

Clarifying questions to ask

1. Do intervals that share an endpoint overlap? (No.)
2. Do I return the count or the removed intervals? (The count.)
3. Is the input sorted? (No.)

Follow-ups to expect

1. "Why is it the same as maximising the kept intervals?"
2. "Why sort by end, not start?"
3. "How is this related to the minimum number of arrows to burst balloons?"
4. "Can you sort by start instead?"
5. "Complexity?"

Related questions

• Insert Interval Medium
• Merge Intervals Medium
• Assign Cookies Easy
• Sort an array of 0's 1's and 2's Medium
• Kadane's Algorithm Medium
• 3 Sum Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in