Last active
May 23, 2020 11:52
-
-
Save Gowtham-369/0de2156d3350ad3dbe2d603459940f7b to your computer and use it in GitHub Desktop.
Day 22:LeetCode 30 Day May Challenges
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) { | |
//already sorted intervals | |
//vector<pair<int,int>> u; | |
//vector<pair<int,int>> v; | |
vector<vector<int>> ans; | |
//have to handle empty cases | |
int m = A.size(); | |
//for(int i=0; i<m; i++){ | |
//u.push_back({A[i][0],A[i][1]}); | |
//} | |
int n = B.size(); | |
//for(int i=0; i<n; i++){ | |
//v.push_back({B[i][0],B[i][1]}); | |
//} | |
//m = u.size(); | |
//n = v.size(); | |
//u[i].second <=> A[i][1] | |
//u[i].first <=> A[i][0] | |
//v[j].second <=> B[i][1] | |
//v[j].first <=> B[i][0] | |
for(int i=0; i<m; i++){ | |
for(int j=0; j<n; j++){ | |
//three main cases | |
if(A[i][0] > B[j][0]) | |
continue;//no intersection yet | |
else if(A[i][1] >= B[j][0] && A[i][0]<= B[j][0]){ | |
vector<int> w; | |
w.push_back(B[j][0]); | |
w.push_back(min(A[i][1],B[j][1])); | |
ans.push_back(w); | |
} | |
else if(A[i][0]>= B[j][0] && A[i][1] <= B[j][1]){ | |
vector<int> w; | |
w.push_back(A[i][0]); | |
w.push_back(A[i][1]); | |
ans.push_back(w); | |
} | |
else if(A[i][0] <= B[j][1] && A[i][1] >= B[j][1]){ | |
vector<int> w; | |
w.push_back(max(A[i][0],B[j][0])); | |
w.push_back(B[j][1]); | |
ans.push_back(w); | |
} | |
else{ | |
if(A[i][1] < B[j][0]) | |
break; | |
} | |
} | |
} | |
return ans; | |
} | |
}; | |
/* | |
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) { | |
//already sorted intervals | |
vector<pair<int,int>> u; | |
vector<pair<int,int>> v; | |
vector<vector<int>> ans; | |
//have to handle empty cases | |
int m = A.size(); | |
for(int i=0; i<m; i++){ | |
u.push_back({A[i][0],A[i][1]}); | |
} | |
int n = B.size(); | |
for(int i=0; i<n; i++){ | |
v.push_back({B[i][0],B[i][1]}); | |
} | |
m = u.size(); | |
n = v.size(); | |
for(int i=0; i<m; i++){ | |
for(int j=0; j<n; j++){ | |
//three cases | |
if(u[i].second >= v[j].first && u[i].first <= v[j].first){ | |
vector<int> w; | |
w.push_back(v[j].first); | |
w.push_back(min(u[i].second,v[j].second )); | |
ans.push_back(w); | |
} | |
else if(u[i].first >= v[j].first && u[i].second <= v[j].second){ | |
vector<int> w; | |
w.push_back(u[i].first); | |
w.push_back(u[i].second); | |
ans.push_back(w); | |
} | |
else{ | |
if(u[i].first <= v[j].second && u[i].second >= v[j].second){ | |
vector<int> w; | |
w.push_back(max(u[i].first,v[j].first)); | |
w.push_back(v[j].second); | |
ans.push_back(w); | |
} | |
} | |
} | |
} | |
return ans; | |
} | |
*/ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. | |
Return the intersection of these two interval lists. | |
(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].) | |
Example 1: | |
Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]] | |
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] | |
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists. | |
Note: | |
0 <= A.length < 1000 | |
0 <= B.length < 1000 | |
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9 | |
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment