LeetCode 986 Interval List Intersections
概述
https://leetcode.com/problems/interval-list-intersections/
直接法
枪打出头鸟，每次只处理最靠前那个。
时间复杂度 O(n)。
class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
int i = 0, j = 0;
vector<vector<int>> ans;
while (i < firstList.size() && j < secondList.size()) {
auto front = firstList[i];
auto back = secondList[j];
bool frontIsI = true;
if (front[0] > back[0]) {
front = secondList[j];
back = firstList[i];
frontIsI = false;
}
if (front[1] < back[0]) {
frontIsI ? i ++ : j ++;
continue;
}
if (back[1] <= front[1]) {
ans.push_back(back);
frontIsI ? j ++ : i ++;
} else {
ans.push_back({back[0], front[1]});
frontIsI ? i ++ : j ++;
}
}
return ans;
}
};