# 986. Interval List Intersections 区间列表的交集

@TOC

## # 题目描述

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:

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

## # 解题方法

### # 双指针

``````/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> intervalIntersection(vector<Interval>& A, vector<Interval>& B) {
vector<Interval> res;
const int M = A.size();
const int N = B.size();
if (M == 0 || N == 0) return res;
int ai = 0, bi = 0;
while (ai != M && bi != N) {
Interval a = A[ai];
Interval b = B[bi];
if (a.end < b.start) {
++ai;
} else if (a.start > b.end) {
++bi;
} else {
res.push_back({max(a.start, b.start), min(a.end, b.end)});
if (a.end <= b.end) {
++ai;
} else {
++bi;
}
}
}
return res;
}
};
``````

## # 日期

2019 年 2 月 19 日 —— 重拾状态