DEV Community

Cover image for Leetcode 435. Non-overlapping Intervals
blakeahalt
blakeahalt

Posted on

Leetcode 435. Non-overlapping Intervals

Description

This solution works by first sorting the intervals array in ascending order based on the starti of each interval.

intervals.sort((a,b)=> a[0]-b[0])
Enter fullscreen mode Exit fullscreen mode

The sorted array becomes:
intervals = [[1,2],[1,3],[2,3],[3,4]]

Here is a simple way to visualize the intervals array:

intervals array

Next, we initialize a variable called prevEnd to the endi of the first interval, or intervals[0][1], and a variable called count to 0.

let prevEnd = intervals[0][1]
let count = 0
Enter fullscreen mode Exit fullscreen mode

Here is what that looks like:

first code

For loops typically begin at i=0, but notice our for loop begins at i=1.

 for (let i=1; i<intervals.length; i++) {
...
}
Enter fullscreen mode Exit fullscreen mode

This is because we've already used the first element of the intervals array, which represents i=0, to set the variable prevEnd = intervals[0][1]. In our case, prevEnd is initialized at 2.

image3

So starting at i=1, every iteration of the for loop compares the values between intervals[i][0] and prevEnd to determine which code in the if/else statement to execute. Note that the value of prevEnd will get updated each iteration.

if/else

If intervals[i][0] is greater than or equal to prevEnd, it means that the interval does not overlap with the previous interval and prevEnd is updated to the endi of the current interval, or intervals[i][1].

if (intervals[i][0] >= prevEnd) {
  prevEnd = intervals[i][1]
...
Enter fullscreen mode Exit fullscreen mode

Else, if intervals[i][0] is less than prevEnd, it means that the interval overlaps with the previous interval. So, the variable count is incremented by one and prevEnd is updated to the minimum value between intervals[i][1] and prevEnd.

...
else
  count++
  prevEnd = Math.min(intervals[i][1], prevEnd)
}
Enter fullscreen mode Exit fullscreen mode

Let's walk through the for loop and see how the if/else statement gets applied at each iteration.

In the first iteration, when i=1, we can see that intervals[i][0] <= prevEnd.

i=1

According to the if/else statement, we increment the count by 1 and set prevEnd to the smaller value between intervals[i][1] and prevEnd. In this case intervals[1][1]=3 and prevEnd=2, so prevEnd remains the same.

if statement

In the next iteration when i=2, prevEnd = intervals[i][0].

i=2

According to the if/else statement, we set prevEnd to intervals[i][1]. In this case intervals[2][1]=3, so prevEnd updates its value to 3.

else statement

In the last iteration when i=3, prevEnd = intervals[i][0] once again.

i=3

Since, there are no more iterations, we exit the for loop and return our count, which is 1.

A visual review of our process shows that removing the second element of the array makes the rest of the array non-overlapping.

visual review

The time complexity is O(nlog n), where n is the number of intervals in the input array. This is because the code first sorts the input array, which takes O(nlog n) time, and then iterates through the array once, performing constant-time operations on each element.

The space complexity is O(1), which means that the amount of memory used by the code is constant, regardless of the size of the input. This is because the code only uses a few constant-size variables to store information, and does not create any new arrays or objects.

Hope this was helpful.

Happy coding!

Top comments (0)