Remove Covered Intervals

Remove Covered Intervals

Remove Covered Intervals - LeetCode

- 문제 내용 :

[min,max]의 배열로 된 2중 Array를 줄경우 [min,max]내에 존재하는 타 [min', max'] Array를 삭제 하라

 

- 접근 방법

Greedy 알고리즘을 사용해서 접근하면 되는데, sorting 문제라고 생각하면 된다.

min이 가장 작은 순서대로 sorting을 하는데, 만약 min이 같은 경우에는  max가 가장 큰 순서대로 정렬을 시킨다.

코드로 보면 아래와 같다.

    intervals.sort((a,b)=> {
        let diff = a[0] - b[0];
        if(diff === 0){
            return b[1] - a[1];
        } else {
            return diff;
        }
    });

min값이 유지 되는한 max가 가장 큰값을 left-right 범위로 해서 뒤에 있는 [min,max] 와 비교하면 된다.

var removeCoveredIntervals = function(intervals) {
    if(intervals.length === 0) return 0;
    intervals.sort((a,b)=> {
        let diff = a[0] - b[0];
        if(diff === 0){
            return b[1] - a[1];
        } else {
            return diff;
        }
    });

    let index = 1;
    let left = intervals[0][0];
    let right = intervals[0][1];
    let count = intervals.length;

    while (index < intervals.length) {
        let [tmpLeft, tmpRight] = intervals[index];
        if (left <= tmpLeft && tmpRight <= right) {
            count--;
        } else {
            left = tmpLeft;
            right = tmpRight;
        }
        index++;
    }

    return count;
};

비교의 범위를 벗어나게 되면 즉시 left와 rigth를 update해준다.

갑작이 이거 보러 오시는 분들이 많아서 오랫만에 다시 문제를 풀어봤다.

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var removeCoveredIntervals = function(intervals) {
    let result = new Array();
    
    intervals.sort((a,b)=>{
        if(a[0] !== b[0]) return a[0] - b[0];
        if(a[0] === b[0]) return b[1] - a[1];
    });
    
    let comparated = intervals[0];
    let position = 1;
    let count = 1;
    
    while(position < intervals.length){
        const next = intervals[position];
        if(!(next[0] >= comparated[0] && next[1] <= comparated[1])){
            count++;
            comparated = next;
        }
        
        position++;
    }
    return count;
};

 

시간복잡도

sorting이 있기 때문에 $ O(NlogN) $ 이다