986. Interval List Intersections

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]]
``````

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`

``````class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
int m = A.size(), n = B.size(), i = 0, j = 0;
vector<vector<int>> res;
while (i < m && j < n) {
if (A[i][1] < B[j][0]) {
++i;
} else if (B[j][1] < A[i][0]) {
++j;
} else {
res.push_back({max(A[i][0], B[j][0]), min(A[i][1], B[j][1])});
if (A[i][1] < B[j][1]) ++i;
else if (B[j][1] < A[i][1]) ++j;
else {++i; ++j;}
}
}
return res;
}
};
``````

``````class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
int m = A.size(), n = B.size(), i = 0, j = 0;
vector<vector<int>> res;
while (i < m && j < n) {
int lo = max(A[i][0], B[j][0]), hi = min(A[i][1], B[j][1]);
if (lo <= hi) res.push_back({lo, hi});
(A[i][1] < B[j][1]) ? ++i : ++j;
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/986

Merge Intervals

Merge Sorted Array

Employee Free Time

https://leetcode.com/problems/interval-list-intersections/

https://leetcode.com/problems/interval-list-intersections/discuss/231108/C%2B%2B-O(n)-"merge-sort"

https://leetcode.com/problems/interval-list-intersections/discuss/646988/C%2B%2B-or-Easy-or-6-lines-or-Two-pointer-or-100

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation