blakeahalt

Posted on

# Leetcode 435. Non-overlapping Intervals

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])
``````

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