---
# System prepended metadata

title: 435 Non-overlapping Interval
tags: [Medium, Intervals]

---

## Question

>[Leetcode.435 Non-overlapping Intervals
](https://leetcode.com/problems/non-overlapping-intervals/description/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

```
- Time complexity: O()
- Space complexity: O()
```
:::

<br>

## Thoughts & Solutions



### YC
:::spoiler Code
```javascript=
/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    // Sort the array according to the value of the minimum number of intervals (left side)
    intervals.sort((a,b)=> a[0]-b[0]);
    let currEnd = Number.NEGATIVE_INFINITY;
    let count = 0;
    for(const [start, end] of intervals){
        if(currEnd <= start){
            currEnd = end;
        }else{
            // overlap
            count++;
            currEnd = Math.min(currEnd, end);
        }
    }

    return count;
};

```
:::

<hr/>



### Sol

![Screenshot 2024-06-04 at 10.17.43 PM](https://hackmd.io/_uploads/SkjEfj24A.jpg)

:::spoiler Code
```javascript=
var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a,b)=>a[1]-b[1])
    let pre = intervals[0];
    let remove = 0;
    for(let i = 1;  i<intervals.length; i++){
        const [start] = intervals[i]
        if(start < pre[1]) remove++;
         else pre = intervals[i]
    }
    return remove
};

```
:::

<hr/>

### 東
![Screenshot 2024-05-30 at 16.37.29](https://hackmd.io/_uploads/BkTjc3BNR.png)

:::spoiler Code
```javascript=
// Time - O(nlogn) | Space - O(1) -- n is the number of input intervals
var eraseOverlapIntervals = function(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    
    let removeCount = 0;
    let accuEnd = intervals[0][1];
    for(let i = 1; i < intervals.length; i++) {
        const [start, end] = intervals[i];
        if(start < accuEnd) {
            removeCount++;
            accuEnd = Math.min(end, accuEnd);
        } else {
            accuEnd = end;
        }
    }

    return removeCount;
};
```
:::

<hr/>

### Jessie

:::spoiler Code
```javascript=

```
:::

<hr/>


<br>

## Live Coding

:::spoiler (name)
```
// write your code here
```
:::