435. Remove overlapping

#include <stdlib.h>

static int cmpIntervals(const void *a, const void *b) {
  const int *x = *(int *const *)a, *y = *(int *const *)b;
  if (x[0] != y[0])
    return x[0] < y[0] ? -1 : 1;
  return x[1] < y[1] ? -1 : x[1] > y[1];
}

int eraseOverlapIntervals(int **intervals, int intervalsSize,
                          int *intervalsColSize) {
  (void)intervalsColSize;
  qsort(intervals, intervalsSize, sizeof(int *), cmpIntervals);
  int kept = 0;
  int lastEnd = 0; // end of the last kept interval

  for (int i = 0; i < intervalsSize; i++) {
    if (kept == 0 || lastEnd <= intervals[i][0]) {
      kept++;
      lastEnd = intervals[i][1];
    } else if (lastEnd > intervals[i][1]) {
      lastEnd = intervals[i][1]; // overlap: keep the one that ends earlier
    }
  }

  return intervalsSize - kept;
}

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
  int eraseOverlapIntervals(vector<vector<int>> &intervals) {
    vector<vector<int>> result;
    sort(intervals.begin(), intervals.end());

    for (int i = 0; i < intervals.size(); i++) {
      if (result.empty() || result.back()[1] <= intervals[i][0]) {
        result.push_back(intervals[i]);
        continue;
      }

      if (result.back()[1] > intervals[i][1]) {
        result.pop_back();
        result.push_back(intervals[i]);
      }
    }

    return intervals.size() - result.size();
  }
};

package intervals

import "slices"

func eraseOverlapIntervals(intervals [][]int) int {
    slices.SortFunc(intervals, func(a, b []int) int {
        if a[0] != b[0] {
            return a[0] - b[0]
        }
        return a[1] - b[1]
    })
    kept := 0
    lastEnd := 0 // end of the last kept interval

    for _, cur := range intervals {
        if kept == 0 || lastEnd <= cur[0] {
            kept++
            lastEnd = cur[1]
        } else if lastEnd > cur[1] {
            lastEnd = cur[1] // overlap: keep the one that ends earlier
        }
    }

    return len(intervals) - kept
}

import java.util.Arrays;

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        int kept = 0;
        int lastEnd = 0; // end of the last kept interval

        for (int[] cur : intervals) {
            if (kept == 0 || lastEnd <= cur[0]) {
                kept++;
                lastEnd = cur[1];
            } else if (lastEnd > cur[1]) {
                lastEnd = cur[1]; // overlap: keep the one that ends earlier
            }
        }

        return intervals.length - kept;
    }
}

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function (intervals) {
  intervals.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  let kept = 0;
  let lastEnd = 0; // end of the last kept interval

  for (const [start, end] of intervals) {
    if (kept === 0 || lastEnd <= start) {
      kept++;
      lastEnd = end;
    } else if (lastEnd > end) {
      lastEnd = end; // overlap: keep the one that ends earlier
    }
  }

  return intervals.length - kept;
};

from typing import List


class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        kept = 0
        lastEnd = 0  # end of the last kept interval

        for start, end in intervals:
            if kept == 0 or lastEnd <= start:
                kept += 1
                lastEnd = end
            elif lastEnd > end:
                lastEnd = end  # overlap: keep the one that ends earlier

        return len(intervals) - kept

impl Solution {
    pub fn erase_overlap_intervals(mut intervals: Vec<Vec<i32>>) -> i32 {
        intervals.sort();
        let mut kept = 0;
        let mut last_end = 0; // end of the last kept interval

        for cur in &intervals {
            if kept == 0 || last_end <= cur[0] {
                kept += 1;
                last_end = cur[1];
            } else if last_end > cur[1] {
                last_end = cur[1]; // overlap: keep the one that ends earlier
            }
        }

        intervals.len() as i32 - kept
    }
}