# 【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++`