給定兩個由一些 閉區(qū)間 組成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而?secondList[j] = [startj, endj] 。每個區(qū)間列表都是成對 不相交 的，并且 已經(jīng)排序 。

返回這 兩個區(qū)間列表的交集 。

形式上，閉區(qū)間?[a, b]（其中?a <= b）表示實數(shù)?x?的集合，而?a <= x <= b 。

兩個閉區(qū)間的 交集 是一組實數(shù)，要么為空集，要么為閉區(qū)間。例如，[1, 3] 和 [2, 4] 的交集為 [2, 3] 。

示例 1：

輸入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
輸出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
示例 2：

輸入：firstList = [[1,3],[5,9]], secondList = []
輸出：[]
示例 3：

輸入：firstList = [], secondList = [[4,8],[10,12]]
輸出：[]
示例 4：

輸入：firstList = [[1,7]], secondList = [[3,10]]
輸出：[[3,7]]
?

提示：

0 <= firstList.length, secondList.length <= 1000
firstList.length + secondList.length >= 1
0 <= starti < endi <= 109
endi < starti+1
0 <= startj < endj <= 109
endj < startj+1

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/interval-list-intersections
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解題報告：

O(n^2)的方法就不說了。

來說個O(n)的。

for遍歷第一個vector，然后用pos指針去遍歷第二個vector。

因為隨著for遍歷，pos也會一直增大，是單調(diào)的，所以復雜度是On的。

class Solution { public:vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {vector<vector<int>> ans;int pos = 0;for(int i = 0; i<firstList.size(); i++) {int l = firstList[i][0], r = firstList[i][1];//先把不相交的給過濾掉while(pos < secondList.size() && secondList[pos][1]<l) pos++;//完全相交的while(pos < secondList.size() && secondList[pos][1]<=r) {ans.push_back(vector<int>{max(l, secondList[pos][0]), secondList[pos][1]});pos++;}if(pos < secondList.size() && secondList[pos][0] <= r) {//這里不要落下等號ans.push_back(vector<int>{max(l, secondList[pos][0]), r});}}return ans;} };

題解是個更簡單的方法：用類似O(n^2)的暴力判斷，只不過這題比較巧，可以雙指針來優(yōu)化掉一些區(qū)間。

有空寫寫看。

總結(jié)

以上是生活随笔為你收集整理的【LeetCode 986】 区间列表的交集（区间交集）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。