美文网首页
俩数组区间交集

俩数组区间交集

作者: 小幸运Q | 来源:发表于2021-05-23 21:17 被阅读0次

image.png

双指针,注意单个数组的前面可能重叠,后面也可能。

遇到 [1,3],[2,4]这种重叠的记得left指针要抛弃[1,3]这种end更小的然后left++,因为下一个重叠肯定跟[1,3]没关系了。

如果没有重叠那就把前面那个指针++。

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
        if(firstList.size()==0||secondList.size()==0){
            return {};
        }
        int l1=0;
        int l2=0;
        vector<vector<int>>res;
        // 看谁的start更小,然后判断是否有交集,有交集那么start更小但是end也更小的抛弃然后l1++,否则抛弃l2
        while(l1<firstList.size()&&l2<secondList.size()){
            int p1=max(firstList[l1][0],secondList[l2][0]);
            int p2=min(firstList[l1][1],secondList[l2][1]);
            if(p1<=p2){
                res.push_back(vector<int>{p1,p2});
                if(firstList[l1][1]<secondList[l2][1]){
                    l1++;
                }else{
                    l2++;
                }
            }else{
                if(firstList[l1][1]<secondList[l2][0]){
                    l1++;
                }
                else{
                    l2++;
                }
            }
        }
        return res;
    }
};

相关文章

  • 俩数组区间交集

    双指针,注意单个数组的前面可能重叠,后面也可能。 遇到 [1,3],[2,4]这种重叠的记得left指针要抛弃[1...

  • 区间调度之区间交集问题

    读完本文,你可以去力扣拿下如下题目: 986.区间列表的交集[https://leetcode-cn.com/pr...

  • Kotlin 学习四

    一: 区间、数组、集合① 区间(或叫作范围) ② 数组 Array ③ 集合 二: for 循环语句 三:whil...

  • 力扣 57 插入区间

    题意:给一个区间数组,和一个区间,把那个区间插入区间数组 思路:遍历每一个interval 如果当前interva...

  • 三种一维树状数组

    单点修改+区间查询 最基本的树状数组 树状数组入门 模板(洛谷P3374 【模板】树状数组1) 区间修改+单点查询...

  • 力扣 239 滑动窗口最大值

    题意:给定一个数组和一个区间,在数组上,从头开始移动区间,返回移动过程中区间的最大值 思路:遍历数组,用双向队列来...

  • 归并排序(Java版)

    归并排序:当数组只有四个元素的时候可以这样定义归并排序,将数组平均分成两半,分别是左区间和右区间,将左区间、右区间...

  • 区间贪心算法

    给出N个开区间(x,y),从中选择尽可能多的开区间,使得这些开区间两两没有交集。 区间被包含,选择区间长度短的 区...

  • 数组的交差并&去重

    数组去重 数组交集 数组并集 数组差集

  • 线段树 + 树状数组 + ST表 模板

    线段树 区间修改+区间求和 logN 树状数组 区间求和+单点修改 logN ST表 离线查询区间最值 构造Nlo...

网友评论

      本文标题:俩数组区间交集

      本文链接:https://www.haomeiwen.com/subject/cmlzjltx.html