Non Overlapping Intervals

Osgood Gunawan
Jan 11 · 3 min read

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.

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!

The Startup

Get smarter at building your thing. Join The Startup’s +791K followers.

Sign up for Top 10 Stories

By The Startup

Get smarter at building your thing. Subscribe to receive The Startup's top 10 most read stories — delivered straight into your inbox, once a week. Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +791K followers.

Osgood Gunawan

Written by

UX designer | Software Engineer | Dancer | Always a student. https://www.osgoodgunawan.me/

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +791K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store