This is one of those problems where the clean idea matters more than the amount of code. For 1288. Remove Covered Intervals, the solution in this repository is mainly a two pointers solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: two pointers, greedy.
The notes already sitting in the source point us in the right direction:
- WA: 6 / 32 test cases passed.
- [[34335,39239],[15875,91969],[29673,66453],[53548,69161],[40618,93111]]
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are isCovered, removeCoveredIntervals.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(NlogN), space: O(1)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//WA: 6 / 32 test cases passed.
02//[[34335,39239],[15875,91969],[29673,66453],[53548,69161],[40618,93111]]
03//Runtime: 24 ms, faster than 76.60% of C++ online submissions for Remove Covered Intervals.
04//Memory Usage: 10.5 MB, less than 100.00% of C++ online submissions for Remove Covered Intervals.
05class Solution {
06public:
07 bool isCovered(int a, int b, int c, int d){
08 //check whether [a,b) is covered by [c,d)
09 return c <= a && b <= d;
10 };
11
12 int removeCoveredIntervals(vector<vector<int>>& intervals) {
13 int covered = 0;
14 int N = intervals.size();
15
16 for(int i = 0; i < N; i++){
17 for(int j = 0; j < N; j++){
18 if(i != j && isCovered(intervals[i][0], intervals[i][1], intervals[j][0], intervals[j][1])) covered++;
19 }
20 }
21
22 return N-covered;
23 }
24};
25
26//sort, one pass
27//https://leetcode.com/problems/remove-covered-intervals/discuss/451277/JavaC%2B%2BPython-Sort-Solution-Test-Cases-are-Trash
28//time: O(NlogN), space: O(1)
29//Runtime: 24 ms, faster than 76.60% of C++ online submissions for Remove Covered Intervals.
30//Memory Usage: 11.1 MB, less than 100.00% of C++ online submissions for Remove Covered Intervals.
31class Solution {
32public:
33 int removeCoveredIntervals(vector<vector<int>>& intervals) {
34 int res = 0, left = -1, right = -1;
35 sort(intervals.begin(), intervals.end());
36 for(vector<int>& v : intervals){
37 //v[0] same as left: remove last interval
38 //v[0] bigger, v[1] same as right: remove current interval
39 if(v[0] > left && v[1] > right){
40 //later interval can only has left and right boundary >= current left and right boundary
41 //so update "left"
42 left = v[0];
43 //current interval is not covered, so add it
44 res++;
45 }
46 //v[0] same as left: remove last interval and make right bigger
47 //v[0] bigger, v[1] same as right: right is not changed
48 right = max(right, v[1]);
49 }
50 return res;
51 }
52};
53
54//revise from https://leetcode.com/problems/remove-covered-intervals/discuss/451277/JavaC%2B%2BPython-Sort-Solution-Test-Cases-are-Trash
55//easier to understand
56//Runtime: 52 ms, faster than 66.90% of C++ online submissions for Remove Covered Intervals.
57//Memory Usage: 11.5 MB, less than 57.75% of C++ online submissions for Remove Covered Intervals.
58//time: O(NlogN), space: O(1)
59class Solution {
60public:
61 int removeCoveredIntervals(vector<vector<int>>& intervals) {
62 int res = 0, left = -1, right = -1;
63 sort(intervals.begin(), intervals.end());
64 for(vector<int>& v : intervals){
65 //v[0] can only >= left
66 if(v[0] == left){
67 //v[1] can only >= right
68 if(v[1] == right){
69 //the two intervals are exactly the same
70 //discard current interval
71 }else{
72 //v[1] > right
73 //last interval is covered by current interval
74 right = v[1];
75 }
76 }else{
77 //v[0] > left
78 if(v[1] <= right){
79 //current interval is covered by last interval
80 }else{
81 //v[1] > right
82 //the two intervals cannot cover each other
83 left = v[0];
84 right = v[1];
85 ++res;
86 }
87 }
88 }
89 return res;
90 }
91};
92
93//sort left ascending, right descending
94//Runtime: 44 ms, faster than 89.91% of C++ online submissions for Remove Covered Intervals.
95//Memory Usage: 11.6 MB, less than 50.00% of C++ online submissions for Remove Covered Intervals.
96//time: O(NlogN), space: O(1)
97class Solution {
98public:
99 int removeCoveredIntervals(vector<vector<int>>& intervals) {
100 //sort left ascending, right descending
101 sort(intervals.begin(), intervals.end(),
102 [](const vector<int>& a, const vector<int>& b){
103 return (a[0] == b[0]) ? a[1] > b[1] : a[0] < b[0];
104 });
105
106 int res = 0, right = -1;
107
108 for(const vector<int>& v : intervals){
109 if(v[1] > right){
110 //in this case v[1] > right and v[0] > left
111 ++res;
112 right = v[1];
113 }
114 /*
115 ignore these cases:
116 1. v[0]==left && v[1]<=right:
117 these intervals are covered by last interval
118 2. v[0]>left && v[1]<=right:
119 these intervals are covered by last interval
120 */
121 }
122
123 return res;
124 }
125};Cost
Complexity
Time
O(NlogN), space: O(1)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.