题目描述：
给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
返回这 两个区间列表的交集 。
形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
数据范围：
$0\le firstList.len, secondList.len \le 1000$
题解：
不像单个列表的合并，多个列表的合并有点麻烦。但是可以发现只有两个列表中的一段区间相交时才会需要更新答案。所以先跳过不相交的部分。
也就是二者完全不相交， $firstList[i][1] < secondList[j][0] || first[i][0] > secondList[j][1]$ ，并且谁在更前面，谁就要往后移动。
然后就是相交部分，相交部分直接更新答案，然后根据区间末尾的大小关系，移动指针。
也可以直接先取最大值，最小值得到区间，判断区间是否合法。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<vector<int>> intervalIntersection(vector<vector<int>> &firstList, vector<vector<int>> &secondList)
{
if (firstList.size() == 0 || secondList.size() == 0)
return {};
int size1 = firstList.size(), size2 = secondList.size();
int i = 0, j = 0;
vector<vector<int>> ans;
while (i < size1 && j < size2)
{
if (firstList[i][1] < secondList[j][0])
{
++i;
continue;
}
if (secondList[j][1] < firstList[i][0])
{
++j;
continue;
}
ans.push_back({max(firstList[i][0], secondList[j][0]), min(firstList[i][1], secondList[j][1])});
if (firstList[i][1] < secondList[j][1])
++i;
else
++j;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<vector<int>> intervalIntersection(vector<vector<int>> &firstList, vector<vector<int>> &secondList)
{
if (firstList.size() == 0 || secondList.size() == 0)
return {};
int size1 = firstList.size(), size2 = secondList.size();
int i = 0, j = 0;
vector<vector<int>> ans;
while (i < size1 && j < size2)
{
int x = max(firstList[i][0], secondList[j][0]);
int y = min(firstList[i][1], secondList[j][1]);
if (x <= y)
ans.push_back({max(firstList[i][0], secondList[j][0]), min(firstList[i][1], secondList[j][1])});
if (firstList[i][1] < secondList[j][1])
++i;
else
++j;
}
return ans;
}
};
|