The Blind 75 Leetcode Series: Non-overlapping Intervals

Photo by Chris Ried on Unsplash

435. Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

We are given a list of intervals consisting 2 elements. We want to see how many intervals we have to remove in order to make the list not overlapping.

We want to make sure of some things:

1. are the intervals only consisting of integers?
2. are we expecting empty intervals?

If the interviewer tells us we shouldn’t expect empty intervals and intervals all consist only integers, then we can start.

Do you remember the meeting room question? In that question, we want to check if there’s any conflict in the meetings. It’s the same as saying we should check for overlapping intervals. Thus, we can use the same methods to find the overlaps. Then we just need to check how many we have to remove.

We need to sort the intervals in ascending order to line them up. We can sort by the earliest end time to latest…