Sponsored
Sponsored
First, sort the intervals by their starting point. If two intervals have the same start, sort them by their ending point in descending order. This helps in ensuring that when you iterate, you can simply keep a check on the maximum end encountered and compare each interval to determine if it is covered.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is done in place.
1import java.util.*;
2class Solution {
3 public int removeCoveredIntervals(int[][] intervals) {
4 Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
5 int remaining = 0, prevEnd = 0;
6 for (int[] interval : intervals) {
7 if (interval[1] > prevEnd) {
8 remaining++;
9 prevEnd = interval[1];
10 }
11 }
12 return remaining;
13 }
14}The Java solution uses Arrays.sort along with a comparator to sort the interval array as needed. Then, it loops through to verify if each interval is not covered using the same method as before, tracking the number of remaining intervals.
Conceptually, treat each pair of intervals as a directed edge if one interval is covering another. Such implicit graph construction helps identify covered intervals. You process over this graph to recognize unique intervals not covered by others. This approach may be non-trivial compared to the sorting technique, but it provides a different perspective.
Time Complexity: O(n^2) for comparing each interval with every other one.
Space Complexity: O(n) for the boolean array tracking covered intervals.
1using namespace std;
bool isCovered(const vector<int>& a, const vector<int>& b) {
return b[0] <= a[0] && a[1] <= b[1];
}
int removeCoveredIntervalsGraph(vector<vector<int>>& intervals) {
int remaining = intervals.size();
vector<bool> covered(intervals.size(), false);
for (int i = 0; i < intervals.size(); ++i) {
for (int j = 0; j < intervals.size(); ++j) {
if (i != j && !covered[i] && isCovered(intervals[i], intervals[j])) {
covered[i] = true;
--remaining;
break;
}
}
}
return remaining;
}C++ adopts a similar checking mechanism through nested loops to model the coverage relationship graph. Boolean vector 'covered' facilitates tracking and remaining count decrements for each interval detected as covered.