Day 22:LeetCode 30 Day May Challenges

Interaval_list_Intersections.cpp

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;   
    }
*/

Problem_statement22.txt

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.