Leetcode 1288) Remove Covered Intervals

05 Jun 2021 in Algorithms

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        boolean[] position = new boolean[intervals.length];
        position[0]=true;
        int cnt=intervals.length;

        for(int i=1;i<intervals.length;i++){    
            boolean check=true;
            for(int j=0;j<i;j++){
                if(position[j]){
                    if((intervals[j][0] <= intervals[i][0]) && (intervals[j][1] >= intervals[i][1])){
                        cnt--;
                        break;
                    }else if((intervals[j][0] >=intervals[i][0]) && (intervals[j][1] <= intervals[i][1])){   
                        position[j]=false;
                        position[i]=true;
                        cnt--; 
                        check =false;
                    }
                }
                if(j==i-1){
                    position[i]=true;
                }
            }
        }
        return cnt;
    }

}

다른 답안

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        int count = 0, i, j, a, b;
        for(i=0;i<intervals.length;i++) {
            a = intervals[i][0];
            b = intervals[i][1];
            for(j=0;j<intervals.length;j++)
                if(i != j && intervals[j][0] <= a && b <= intervals[j][1]) {
                    count++;
                    break;
                }
        }
        return intervals.length - count;
    }
}

• Array sort가 신기하기 때문에 가져와 봄.

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int n = intervals.length;
        int i = 0, count = 0;
        while (i < n) {
            count++;
            int j = i+1;
            while (j < n && intervals[j][1] <= intervals[i][1]) j++;
            i = j;
        }
        return count;
    }
}