難度: Medium
類型: Array,Two Pointers,Sweep Line
CPP程式下載: 986.cpp
Topic:
You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
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 are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].
Example 1:
Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Example 2:
Input: firstList = [[1,3],[5,9]], secondList = [] Output: []
Constraints:
0 <= firstList.length, secondList.length <= 1000firstList.length + secondList.length >= 10 <= starti < endi <= 109endi < starti+10 <= startj < endj <= 109endj < startj+1
Consideration:
1. When overlapped, add overlapped range to outList.
2. When secondList[j][1] > firstList[i][1], move i++
3. When secondList[j][1] < firstList[i][1], move j++
4. When secondList[j][1] == firstList[i][1], move both i++ and j++
Code:
class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
//cout << firstList[0][0] << firstList[0][1] << firstList[1][0] << firstList[1][1] << "\n";
vector<vector<int>> outList;
int m, n, i, j=0;
m = firstList.size();
n = secondList.size();
//cout << "m = " << m << ", n = " << n << "\n";
for (i=0;i<m;i++) {
while (j<n)
{
if (secondList[j][0]>firstList[i][1]) {
break;
}
else if (secondList[j][1]<firstList[i][0]) {
j++;
}
else if ((secondList[j][0]<=firstList[i][0]) && (secondList[j][1]==firstList[i][1])) {
j++;
outList.push_back(firstList[i]);
//cout << "1" << "\n";
break;
}
else if ((secondList[j][0]<=firstList[i][0]) && (secondList[j][1]>firstList[i][1])) {
outList.push_back(firstList[i]);
//cout << "2" << "\n";
break;
}
else if ((secondList[j][0]>=firstList[i][0]) && (secondList[j][1]<=firstList[i][1])) {
outList.push_back(secondList[j]);
//cout << "3" << "\n";
j++;
}
else if ((secondList[j][0]<=firstList[i][0]) && (secondList[j][1]<=firstList[i][1])) {
outList.push_back({firstList[i][0], secondList[j][1]});
//cout << "4" << "\n";
j++;
}
else if ((secondList[j][0]>=firstList[i][0]) && (secondList[j][1]>=firstList[i][1])) {
outList.push_back({secondList[j][0], firstList[i][1]});
//cout << "5" << ", start = "<< secondList[j][0] << ",end = " << firstList[i][1] << "\n";
break;
}
else
{
cout << "Should Not Happen! Check it!!" << "\n";
}
}
}
return outList;
}
};
Result:
https://leetcode.com/problems/interval-list-intersections/submissions/1941880393/
Runtime
0msBeats100.00%
Memory
22.86MBBeats85.40%
