This problem looks busy at first, but the accepted solution is built around one steady invariant. For 986. Interval List Intersections, the solution in this repository is mainly a two pointers solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. 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, sliding window.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The solution is organized around the main LeetCode entry point and a few local helpers.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- 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(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//Runtime: 52 ms, faster than 77.74% of C++ online submissions for Interval List Intersections.
02//Memory Usage: 15.7 MB, less than 100.00% of C++ online submissions for Interval List Intersections.
03
04class Solution {
05public:
06 vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
07 int i = 0, j = 0;
08 vector<vector<int>> intersection;
09
10 while(i < A.size() && j < B.size()){
11 // cout << i << " " << j << endl;
12 vector<int> &block1 = A[i], &block2 = B[j];
13 if(block1[0] <= block2[0] && block1[1] >= block2[1]){
14 //block1 contains block2
15 intersection.push_back(block2);
16 }else if(block1[0] >= block2[0] && block1[1] <= block2[1]){
17 //block2 contains block1
18 intersection.push_back(block1);
19 }else if(min(block1[1] - block2[0], block2[1] - block1[0]) >= 0){
20 //block1 and block2 share one part
21 if(block1[1] - block2[0] <= block2[1] - block1[0]){
22 intersection.push_back({block2[0], block1[1]});
23 }else{
24 intersection.push_back({block1[0], block2[1]});
25 }
26 }
27 //wrong!
28 // if(block1[0] < block2[0]){
29 // i++;
30 // }else if(block1[0] > block2[0]){
31 // j++;
32 // }else if(block1[1] > block2[1]){
33 // //two blocks' left boundaries are the same
34 // j++;
35 // }else{
36 // i++;
37 // }
38
39 if(block1[1] < block2[1]){
40 //move the one whose right boundary is smaller
41 i++;
42 }else if(block1[1] > block2[1]){
43 //move the one whose right boundary is smaller
44 j++;
45 }else if(block1[0] <= block2[0]){
46 //two blocks' right boundaries match
47 //, then move the one whose left boundary is smaller
48 i++;
49 }else{
50 //two blocks' right boundaries match
51 //, then move the one whose left boundary is smaller
52 j++;
53 }
54 }
55 // cout << endl;
56
57 return intersection;
58 }
59};
60
61//https://leetcode.com/problems/interval-list-intersections/solution/
62//Runtime: 44 ms, faster than 97.77% of C++ online submissions for Interval List Intersections.
63//Memory Usage: 15.8 MB, less than 96.00% of C++ online submissions for Interval List Intersections.
64//time complexity: O(M+N), space complexity: O(M+N)
65
66class Solution {
67public:
68 vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
69 int i = 0, j = 0;
70 vector<vector<int>> intersection;
71
72 while(i < A.size() && j < B.size()){
73 int low = max(A[i][0], B[j][0]);
74 int high = min(A[i][1], B[j][1]);
75
76 if(low <= high){
77 intersection.push_back({low, high});
78 }
79
80 /*
81 the interval with smaller endpoint
82 cannot intersect with any other intervals,
83 so discard it
84 */
85 if(A[i][1] < B[j][1]){
86 i++;
87 }else{
88 j++;
89 }
90 }
91
92 return intersection;
93 }
94};Cost