Non-overlapping Intervals

문제

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

• 1 <= intervals.length <= 105

• intervals[i].length == 2

• 5 * 104 <= starti < endi <= 5 * 104

풀이

var eraseOverlapIntervals = function(intervals) {
    let answer = 0;
    intervals.sort((a, b) => a[1] - b[1]);
    
    for(let i = 0; i < intervals.length - 1; i++) {
        const [curStart, curEnd] = intervals[i];
        const [nextStart, nextEnd] = intervals[i + 1];
        if(curEnd > nextStart) {
            answer += 1;
            intervals[i + 1] = intervals[i];
        }
    }
    
    return answer;
};

/**
 * @param {number[][]} intervals
 * @return {number}
 */
const getSortedArray = (arr, func) => {
  return [...arr].sort(func);
};

const eraseOverlapIntervals = (intervals) => {
  let answer = 0;

  const sortedIntervals = getSortedArray(intervals, (a, b) => a[1] - b[1]);
  let last = -50000; // 마지막에 기억하고 있는 엔드값.

  sortedIntervals.forEach(([from, to]) => {
    if (from < last) {
      answer += 1;
    } else {
      last = to; // 겹치지 않을 때만 업데이트를 해주는 이유
    }
  });

  return answer;
};