[LeetCode] 1288. Remove Covered Intervals - 문제풀이

Description

간격을 나타내는 배열 intervals이 주어지면 목록의 다른 간격에 포함된 모든 간격을 제거합니다.intervals[i] = [li, ri][li, ri)

간격 [a, b)은 및 인 경우에만 간격에 포함 [c, d)됩니다 .c <= ab <= d

남은 간격의 수를 반환 합니다 .

Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.

The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.

Return the number of remaining intervals.

Example 1:

Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.

Example 2:

Input: intervals = [[1,4],[2,3]]
Output: 1

Constraints:

• 1 <= intervals.length <= 1000
• intervals[i].length == 2
• 0 <= li <= ri <= 10^5
• All the given intervals are unique.

Solution 1. 정렬(Sort)

public int removeCoveredIntervals(int[][] intervals) {

    int len = intervals.length;
    Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]); //앞자리 기준 오름차순 > 뒷자리기준 내림차
    int removedCnt = 0;
    int min = intervals[0][0];
    int max = intervals[0][1];
    for (int i = 1; i < len; i++) {
        if (min <= intervals[i][0] && max >= intervals[i][1]) {
            ++removedCnt;
        } else {
            min = intervals[i][0];
            max = intervals[i][1];
        }
    }
    return len-removedCnt;

}

요소를 앞자리 기준 오름차순, 뒷자리기준 내림차순 형태로 정렬 한 뒤 겹쳐서 커버가 되는 요소일 경우 카운트해서 배열의 길이에서 제외 한 뒤 반환해줍니다.

Reference

Remove Covered Intervals - LeetCode