leetcode 1288) Remove Covered Intervals

LV. Medium 🧐

https://leetcode.com/problems/remove-covered-intervals/

Remove Covered Intervals - LeetCode

 

문제

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.

 

문제 해결법

intervals를 정렬해서 사용하였다.

0번째 인덱스의 intervals의 [0]를 start로, [1]를 end로 설정하고 진행하였다.

intervals를 한 번 돌며 진행하였다. O(1)

• start == interval[i][0] && end <= intervals[i][1] 인 경우는 intervals[i - 1]이 interval[i]에 포함되어 삭제되어야 되므로 ans를 하나 빼주고, end값을 interval[i][1]값으로 변경해준다.
• start != interval[i][0] && end < intervals[i][1] 인 경우는 intervals[i]가 start와 end의 포함되어 삭제해야 되므로 ans를 하나 빼준다.
• start != intervals[i][0] && end > intervals[i][1] 인 경우 intervals[i]가 start와 end의 범위보다 더 큰 범위이므로, start와 end의 값을 intervals[i]의 값으로 변경한다.

위의 조건식들을 다 체크해주면 문제 해결 완료!

 

해결 코드

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
	int removeCoveredIntervals(vector<vector<int>>& intervals) {
		sort(intervals.begin(), intervals.end());

		int start = intervals[0][0];
		int end = intervals[0][1];
		int ans = intervals.size();
		for (int i = 1; i < intervals.size(); ++i) {
			if (start == intervals[i][0] && end <= intervals[i][1]) {
				end = intervals[i][1];
				ans--;
			}
			else if (start != intervals[i][0] && end >= intervals[i][1])
				ans--;
			else if (start != intervals[i][0] && end < intervals[i][1]) {
				start = intervals[i][0];
				end = intervals[i][1];
			}
		}
		return ans;
	}
};