(Interval, Medium) Non-overlapping Intervals

https://leetcode.com/problems/non-overlapping-intervals/description/

최소한으로 제거하는게 목적이기 때문에 end 기준으로 배열을 정렬하는게 중요하다.
start 기준으로 했을 경우 [1,10], [2,3], [4,5], [6,7] 이런 케이스에서 문제가 될 수 있다.

이 경우 end기준 정렬하면 1개([1,10])만 제거하면 되는데,
start 기준 정렬하면 3개([2,3], [4,5], [6,7])를 제거해야 할 수 있기 때문이다.

정렬을 시켜뒀으면 기준값을 잡고 또 index 1부터 순회할 수 있겠다.
정렬된 배열대로 순회하기 때문에 현재 순회 요소의 start가 이전 요소의 end보다 작다면 제거 대상이다 (겹침)

이 조건을 만족하지 않는 경우 기준값을 갱신해나가면 된다.

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 0;
        int end = intervals[0][1];

        for (int i=1; i<intervals.length; i++) {
            int[] current = intervals[i];
            if (current[0] < end) {
                count++;
            } else {
                end = current[1];
            }
        }

        return count;
    }
}