LeetCode 986 Interval List Intersections

标签: 区间问题 LeetCode 发布于:2022-03-01 17:10:51 编辑于:2022-03-02 15:55:05 浏览量:372

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/