【LeetCode】 986. Interval List Intersections

Description

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].)

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.

給予兩個封閉區間的串列，每個區間都成對且不相交，並照順序排列。

回傳兩個區間串列中重疊的部分。

(通常，一個封閉區間[a, b] (其中 a <= b)意味著一個實數集合x且a <= x <= b。兩個封閉區間的重疊區域也是一個實數集合，它可以是空的也可以是一個封閉區間。例如，[1, 3]和[2, 4]的重疊區間就是[2, 3]。)

注意：

• 0 <= A.length < 1000
• 0 <= B.length < 1000
• 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

注意：
輸入格式在2019年4月15日更動，請重置成預設程式碼以得到新的方法。

Example:

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.

Solution

• 以求方便，我先將A和B合併起來並排序。
  • 這樣做其實會變很慢，如果想追求速度就不要。
• 再來我們用out存下第一個區間的尾，然後接下來只有幾種情況：
  • 1. 下個區域沒有重疊，即A[i][0] > out
    • 直接更新out。
  • 2. 下個區域完全被包含，即A[i][1] < out
    • 加入區間。
  • 3. 下個區域部分交疊，即A[i][1] > out
    • 加入區間，並更新out

Code

#define IN 0
#define OUT 1

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> ans;
        if(A.empty() || B.empty()) return ans; 
        A.insert(A.end(), B.begin(), B.end());
        sort(A.begin(), A.end());
        
        int out = A[0][OUT];
        
        for(int i = 1; i < A.size(); i++)
        {
            if(A[i][IN] > out)
            {
                out = A[i][OUT];
            }
            else if(A[i][OUT] > out)
            {
                vector<int> temp(2, 0);
                temp[0] = A[i][IN];
                temp[1] = out;
                ans.push_back(temp);
                out = A[i][OUT];
            }
            else
            {
                ans.push_back(A[i]);
            }
        }
        
        return ans;
    }
};

tags: LeetCode C++