Leetcode 435. Non-overlapping Intervals

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

intervals.sort((a,b)=> a[0]-b[0])

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

Here is a simple way to visualize the intervals array:

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

let prevEnd = intervals[0][1]
let count = 0

Here is what that looks like:

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

 for (let i=1; i<intervals.length; i++) {
...
}

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.

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 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 end_i of the current interval, or intervals[i][1].

if (intervals[i][0] >= prevEnd) {
  prevEnd = intervals[i][1]
...

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)
}

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.

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.

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

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.

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

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.

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!