Non-overlapping Intervals
MediumExtra practice. This problem has no walkthrough slides. Try solving it with the pattern template on your own, and lean on the hints if you get stuck.
Question
You get intervals, a list of intervals that may overlap each other. Find the fewest intervals you'd have to delete from the list so that none of the remaining intervals overlap.
Input: intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Deleting [1, 3] leaves [1, 2], [2, 3], and [3, 4], none of which overlap.
Input: intervals = [[1, 2], [1, 2], [1, 2]]
Output: 2
You need to delete two of the three copies to leave just one.
Input: intervals = [[1, 2], [2, 3]]
Output: 0
These two intervals share the boundary 2 but don't overlap, so nothing needs to be deleted.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Take a moment to understand the problem and think of your approach before you start coding.