精华内容
下载资源
问答
  • 区间交集

    千次阅读 2019-08-01 15:40:15
    区间交集 #include <bits/stdc++.h> using namespace std; int main() { int n, ans = 0; // ans存储最终结果 scanf("%d", &n); vector<pair<int, int>> v1(n), v2(n); //分别存储两个区间...

    区间交集

    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        int n, ans = 0; // ans存储最终结果
        scanf("%d", &n);
        vector<pair<int, int>> v1(n), v2(n); //分别存储两个区间
        for (int i = 0; i < n; ++i)
            scanf("%d%d", &v1[i].first, &v1[i].second);
        for (int i = 0; i < n; ++i)
            scanf("%d%d", &v2[i].first, &v2[i].second);
        for (auto p1 : v1)
            for (auto p2 : v2)
                if (p1.first <= p2.second && p1.second >= p2.first)
                    ans += min(p1.second, p2.second) -
                           max(p1.first, p2.first); //加上重叠区间
        printf("%d", ans);
        return 0;
    }
    
    
    展开全文
  • 区间调度之区间交集问题 区间调度问题共写了3片博客,前两篇重叠区间和区间合并分别讲了区间的最大不相交子集和重叠区间的合并,今天再写一个算法,可以快速找出两组区间的交集。 一、解题思路 解决区间问题的思路...

    区间调度之区间交集问题

    区间调度问题共写了3片博客,前两篇重叠区间区间合并分别讲了区间的最大不相交子集和重叠区间的合并,今天再写一个算法,可以快速找出两组区间的交集

    在这里插入图片描述

    一、解题思路

    解决区间问题的思路一般是先排序,以便操作,不过题目说已经排好序了,那么可以用两个索引指针在 A 和 B 中游走,把交集找出来,代码大概是这样的:

    # A, B 形如 [[0,2],[5,10]...]
    def intervalIntersection(A, B):
        i, j = 0, 0
        res = []
        while i < len(A) and j < len(B):
            # ...
            j += 1
            i += 1
        return res
    

    不难,我们先老老实实分析一下各种情况。

    首先,对于两个区间,我们用 [a1,a2] 和 [b1,b2] 表示在 A 和 B 中的两个区间,那么什么情况下这两个区间没有交集呢

    在这里插入图片描述
    只有这两种情况,写成代码的条件判断就是这样:

    if b2 < a1 or a2 < b1:
        [a1,a2][b1,b2] 无交集
    

    那么,什么情况下,两个区间存在交集呢?根据命题的否定,上面逻辑的否命题就是存在交集的条件:

    # 不等号取反,or 也要变成 and
    if b2 >= a1 and a2 >= b1:
        [a1,a2][b1,b2] 存在交集
    

    接下来,两个区间存在交集的情况有哪些呢?穷举出来:

    在这里插入图片描述

    这很简单吧,就这四种情况而已。那么接下来思考,这几种情况下,交集是否有什么共同点呢?

    在这里插入图片描述

    我们惊奇地发现,交集区间是有规律的!如果交集区间是 [c1,c2],那么 c1=max(a1,b1),c2=min(a2,b2)!这一点就是寻找交集的核心,我们把代码更进一步:

    while i < len(A) and j < len(B):
        a1, a2 = A[i][0], A[i][1]
        b1, b2 = B[j][0], B[j][1]
        if b2 >= a1 and a2 >= b1:
            res.append([max(a1, b1), min(a2, b2)])
        # ...
    

    最后一步,我们的指针 i 和 j 肯定要前进(递增)的,什么时候应该前进呢?

    在这里插入图片描述
    是否前进,只取决于 a2 和 b2 的大小关系。代码:

    while i < len(A) and j < len(B):
        # ...
        if b2 < a2:
            j += 1
        else:
            i += 1
    

    完整代码:

    # A, B 形如 [[0,2],[5,10]...]
    def intervalIntersection(A, B):
        i, j = 0, 0 # 双指针
        res = []
        while i < len(A) and j < len(B):
            a1, a2 = A[i][0], A[i][1]
            b1, b2 = B[j][0], B[j][1]
            # 两个区间存在交集
            if b2 >= a1 and a2 >= b1:
                # 计算出交集,加入 res
                res.append([max(a1, b1), min(a2, b2)])
            # 指针前进
            if b2 < a2: j += 1
            else:       i += 1
        return res
    

    C++代码:

    class Solution {
    public:
        vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
            //保存结果
            vector<vector<int>> ret;
            if(A.empty() || B.empty())
            {
                return ret;
            }
    
            //i和j两个下标索引
            int i = 0;
            int j = 0;
            while(i < A.size() && j < B.size())
            {
                //下面四个变量的含义相见博客
                int a1 = A[i][0];
                int a2 = A[i][1];
                int b1 = B[j][0];
                int b2 = B[j][1];
    
                //代表区间有交集,自己画个图就OK
                if(b2 >= a1 && a2 >= b1)
                {
                    //max(a1,b1),min(a2,b2)两个区间的交集部分
                    ret.push_back({max(a1,b1),min(a2,b2)});
                }
    
                //更新i和j下标索引,b2 < a2 就代表i所在的区间大于j所在的区间,更新j
                //是因为i区间长于j区间的部分还可能和j的下一个区间继续重叠,还需要继续判断
                //所以更新j而不是更新i
                if(b2 < a2)
                {
                    j++;
                }
                else//反之同理
                {
                    i++;
                }
            }   
            return ret;
        }
    };
    

    总结一下,区间类问题看起来都比较复杂,情况很多难以处理,但实际上通过观察各种不同情况之间的共性可以发现规律,用简洁的代码就能处理。

    展开全文
  • 问题 1: 区间交集

    2019-06-05 21:17:00
    问题 1: 区间交集 题目描述 输入 5 个正整数 a1、b1、a2、b2 和 c,如果 c 在区间[a1, b1]内 并且 c 也在区间[a2, b2]内,输出”in”,否则输出...

     

                                                                           

    问题 1: 区间交集

                               

    题目描述

     输入 5 个正整数 a1、b1、a2、b2 和 c,如果 c 在区间[a1, b1]内 并且 c 也在区间[a2, b2]内,输出”in”,否则输出”out”。 

    注意:方括号表示的是闭区间,[a, b]是包括 a 和 b 的。

    输入

    一行 5 个正整数:a1、b1、a2、b2 和 c,范围在[1, 1000000],a1 ≤ b1,a2 ≤ b2。

    输出

    in 或 out。

    样例输入

    4  8  6  10  5

    样例输出

    out

    程序:

    #include<iostream>
    #include<cstdio>
    int main()
    {
    int a1,b1,a2,b2,c;
    scanf("%d%d%d%d%d",&a1,&b1,&a2,&b2,&c);
    if(c>=a1&&c<=b1&&c>=a2&&c<=b2)
    printf("in");
    else
    printf("out");
    return 0;
    }

    转载于:https://www.cnblogs.com/Avengers-666/p/10981992.html

    展开全文
  • 3 区间交集

    2021-05-06 23:05:46
    986. 区间列表的交集 给定两个由一些 闭区间 组成的列表,firstList 和 secondList ,其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的,并且 已经排序 。 ...
    986. 区间列表的交集
    给定两个由一些 闭区间 组成的列表,firstList 和 secondList ,其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的,并且 已经排序 。
    返回这 两个区间列表的交集 。
    形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <= b 。
    两个闭区间的 交集 是一组实数,要么为空集,要么为闭区间。例如,[1, 3][2, 4] 的交集为 [2, 3] 。
    
    示例 1:
    输入:firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
    输出:[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
    示例 2:
    输入:firstList = [[1,3],[5,9]], secondList = []
    输出:[]
    示例 3:
    输入:firstList = [], secondList = [[4,8],[10,12]]
    输出:[]
    示例 4:
    输入:firstList = [[1,7]], secondList = [[3,10]]
    输出:[[3,7]]
    提示:
    
    0 <= firstList.length, secondList.length <= 1000
    firstList.length + secondList.length >= 1
    0 <= starti < endi <= 109
    endi < starti+1
    0 <= startj < endj <= 109
    endj < startj+1
    
    class Solution {
      public int[][] intervalIntersection(int[][] A, int[][] B) {
        //双指针法
        //存放最后的结果
        List<int[]> ans = new ArrayList();
        //定义左右指针
        int i = 0, j = 0;
        //左右指针不越界 一直循环
        while (i < A.length && j < B.length) {
          //新区间的左边界=a b左边界的最大值
          int lo = Math.max(A[i][0], B[j][0]);
          //新区间的右边界=a b区间的右边界的最小值
          int hi = Math.min(A[i][1], B[j][1]);
          //如果 左边界<=右边界 有重叠 添加进结果
          if (lo <= hi)
            ans.add(new int[]{lo, hi});
    
          // 指针移动规则 a的righ < b的right a落后 移动i  否则 b落后 移动j
          if (A[i][1] < B[j][1])
            i++;
          else
            j++;
        }
    
        //List转数组 因为内层int[] 的长度都为2 所以只需要指定 外层的长度即可
        // ans.toArray(new int [ans.size()][] )
        return ans.toArray(new int[ans.size()][]);
      }
    }
    
    展开全文
  • 题意:给你n段区间,让你求这些区间的...分析:求区间交集: 假如min(a[i],b[i]) &lt; max(a[i - 1],b[i - 1]) 那么continue; 现在考虑两种情况: (1)if(a[i] == b[i]) 那么我们计算a[i],,b[i]前边的交集...
  • I - 80-th Level Archeology(前缀和,区间交集) CodeForces - 731D 题意: ​ 给出n个串,一共有c中字母编号为1-c。然后描述每一个串。每一次可以使得所有串的所有字母编号+1(编号为c的变成1).问最少多少次吼...
  • matlab 中连续区间进行交并集操作,输入输出为向量表示的连续区间如A=[a,b,c,d]表示A=(a,b)U(c,d),A为最简表达式,各个集合不相交
  • 题目大意:给n个区间,至多可以去掉一个其中一个区间,最终使得剩下所有区间交集的长度最大,即max(r-l)。且当l==r或交集为空集时,区间长度为0。 初步想法很显然,求L。但问题是确定弃掉的区间。刚开始想着用暴力...
  • 单调区间Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Problem Description百小度最近在逛博客,然后发现了一个有趣的问题。 如下图所示,是一个12位数$014326951987$, 它的...
  • 题意:n段区间,操作一:修改一段区间,操作二:查询下标l~r的区间交集 解析:求交集,就是左端点的最右值~右端点的最左值,线段树维护一下区间最值即可 #include&amp;lt;bits/stdc++.h&amp;gt; using ...
  • 给出N个开区间(X,Y),从中选择尽可能多的开区间,使得这些开区间两两之间没有交集 例如对开区间(1,3),(2,4),(3,5),(6,7)来说,可以选出最多3个区间(1,3),(3,5),(6,7) 思路: 首先对区间进行排序,将x较小的区间排在...
  • 题意:给出n个区间[l,r],选出k个区间,使得这k个区间交集尽量大 n,k 先将区间按照左端点从小到大排序, 枚举k个区间中,左端点最大的为i. 那么剩下k-1个区间 只能在前i-1个区间中选择 显然选右端点前k大的. #...
  • ZCMU-1772-区间交集

    2017-01-02 12:59:36
    1772: Meeting of Old Friends Time Limit:  ...//如果K在区间内,我们就减去1,因为在那个时间它要化妆 printf("%lld\n",count); } else printf("0\n"); } return 0; }
  • 这个题没必要吧问题和时间都恰的那么准,如果第一个人温度的变化区间和第二个人的温度变化区间相交或包含,那么第二个人必定满意,如此类推,每更换一个人就更换一下区间的左右端点,左端点取最大值,右端点取最小值...
  • 内容如下:1)区间完全覆盖问题问题描述:给定一个长度为m的区间,再给出n条线段的起点和终点(注意这里是闭区间),求最少使用多少条线段可以将整个区间完全覆盖样例:区间长度8,可选的覆盖线段[2,6],[1,4],[3,6],[3,...
  • 题意:从0时刻开始,会按时间...设两个客人来访时间相差为mx,那么上一个状态可调节的温度区间就是[last.l - mx, last.r + mx],当前区间为[now.l, now.r],如果两个区间交集,说明可以满足现在这个客人now。如...
  • 很显然,如果一个函数在0到无穷大的区间内积分收敛,即积分结果是一个定值,那么你取0到1000和0到10000积分得到的结果应该很接近,如果说你取了两种相对较大的区间,发现积分结果差别比较大,可能存在两种原因,第一...
  • class Solution { public: vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) { int i=0, j=0;...A.size
  • 题目大意:给你那个区间,问哪些区间断的重叠区间的个数大于等于k,输出最小区间数(要合并) 思路:将左右端点分开(不在一个结构体里)保存在一个数组,加标记确定左端点还是右端点,排序,遇到左端点ans++,右端...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,008
精华内容 403
关键字:

区间交集