This week I encountered many interval questions in binarysearch.com and leetcode. Since I struggle from time to time on this topic, I would love to write a blog regarding interval topics. Today we are going to discuss leetcode #435 Non-overlapping Intervals.
Here is the question:
Intuition and Implementation
There are many ways to solve this question. For me, the first intuition of seeing this problem is a greedy approach (for anyone who does not know what a greedy algorithm is, you can check this article). The greedy strategy comes where we will always try to select the interval with the latest ending point and compare them with the next starting point.
First, we can sort the intervals by their starting points ascendingly. After sorting them based on starting points, we can keep track with two pointers if intervals overlap or not. They are three possibilities of cases while we are traversing the intervals :
- The first case is the easiest, which is when there is non-overlapping between the two intervals. In this case, we only need to move the previous pointer (j) to the next pointer(i), and the count of intervals removed remains unchanged.
2. Second, if the current endpoint is larger than the next index starting point, we know they overlap; we increment the count of intervals (count_remove++, in solution code below ). In this case, the greedy approach is, we can remove the next (later) interval and compare it with the next interval, which means the previous pointer (j) remains unchanged. In contrast, the next pointer keeps traversing to the next one and comparing it with the current interval.
3. Lastly, Another case that we need to consider is if the current endpoint is bigger than the next index endpoint; in this case, we know that they overlap (count_remove++, in solution code below). Since we want the minimum number of intervals to be removed to make the rest of the intervals non-overlapping, we can remain the next (later) interval. Hence, the previous pointer(j) is updated to the current interval(i).
Time & Space complexity
Due to the built-in sorting function, the time complexity is O(n log(n)), and the space complexity is O(1) — no extra space is used.
Thanks for taking the time to read, and I hope you find something helpful!