Non Overlapping Intervals

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:

https://leetcode.com/problems/non-overlapping-intervals/

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 :

1. 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.

first case: [[2,4],[5,8]], there is non-overlapping

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.

The current endpoint is 8, and the next starting point is 7, which we know the intervals overlapping one another. The greedy approach is that we can remove the later interval, which is the [7,9] 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).

Since we want to find the minimum number of intervals, we need to remove them to make the rest of the intervals non-overlapping; therefore, removing interval [1,100] is a better choice.

Solution

solution Leetcode #435 Non-Overlapping intervals in Javascript.

So there you go; that is how you solve Leetcode #435 Non-Overlapping intervals in Javascript.

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!