标签搜索

目 录CONTENT

文章目录

腾讯2020校园招聘----覆盖.md

小小城
2022-05-02 / 0 评论 / 0 点赞 / 10 阅读 / 2,154 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

-覆盖.md
date: 2021-08-22 12:10:10.053
updated: 2021-08-22 12:10:10.053
url: /2021/08/22/腾讯2020校园招聘----覆盖md
categories:
tags:

腾讯2020校园招聘----覆盖

@[toc]

一、题目描述

小Q在进行一场竞技游戏,这场游戏的胜负关键就在于能够能争夺一条长度为L的河道,即可以看作是[0,L]的一条数轴。

这款竞技游戏当中有n个可以提供视野的道具-真视守卫,第i个真视守卫能够覆盖区间[xi,yi]。现在小Q想知道至少用几个真视守卫就可以覆盖整段河道。

输入:

输入包括n+1行。

第一行包括两个整数n和L(1<=n<=10^5,1<=L<=10^9)

接下来的n行,每行两个正整数xi,yi(0<=xi<=yi<=10^9),表示第i个真视守卫覆盖的区间。

输出:

一个整数,表示最少需要的守卫的数量,如果无解,输出-1。

输入例子1:

4 6
3 6
2 4
0 2
4 7

输出例子1:

3

二、问题分析

这是一道典型的贪心算法;

规定区区间为[begin,end]这种形式

首先看一下区间的几种状态
在这里插入图片描述

  •  分析第一种区间的情况,如果出现很多这种重叠的区间,那么我们怎么选择可以选最少的区间覆盖整个L,很显然直接选上面区间长覆盖广的情况
  •  对于第二种区间的情况,如果给出的区间中出现过是这种情况,导致区间没有连接起来无法覆盖整个L,直接返回-1
  •  对于第三种情况,上下两个区间刚好可以构成一个更大的覆盖,如果出现很多这种区间,依次往后增加覆盖长度即可

第一步:按区间的begin升序排序,如果beigin相等,按end降序排序

sort( nums.begin(), nums.end(), [](vector<int>&a, vector<int>&b)
             {
                return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
             });

排序更好的解决第一种区间的问题,直接获取最大的区间

第二步:遍历数组,如果发现出现第二中区间的情况,直接返回-1

if (i < nums.size() && nums[i][0] > begin )
{
    ret = -1;
    break;
}

第三步:对于第三种区间的情况,我们不断选取重叠区间中end最长的,让使用到的区间更少

while( i < nums.size() && nums[i][0] <= begin )
{
    end = max(end, nums[i][1]);
    ++i;
}

在这里插入图片描述

三、代码

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;
   
int main()
{
    int n,L;
    while( cin>>n>>L )
    {
        vector<vector<int>> nums(n,vector<int>(2));
        for ( int i = 0; i < n; ++i )
        {
            cin>>nums[i][0]>>nums[i][1];
        }
        
        //排序
        sort( nums.begin(), nums.end(), [](vector<int>&a, vector<int>&b)
             {
                return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
             });
        
        int begin = 0;//保存每个区间的开始位置
        int i = 0;//遍历的下标索引
        int ret = 0;//保存结果
        int end = 0;//保存每个区间的结束位置
        
        //开始遍历
		while(i < nums.size())
        {  
        	//如果出现本次区间的begin小于等于上一个区间的end,就说明这两个
        	//区间有交集,那么我们需要更新本次区间的end,选取所有处于这种
        	//状态区间中最大最远的end,让覆盖长度更长,区间使用个数更少
            while( i < nums.size() && nums[i][0] <= begin )
            {
                end = max(end, nums[i][1]);
                ++i;
            }
            //更新结果
            ++ret;
			//走到这里说明本次区间的begin已经大于上一区间的end
			//,那么我们直接把begin放到选取中最大的end位置处作为下一次
			//判断区间的开始
            begin = end;

			//如果出现本次区间的开始begin大于上一区间的结束end
			//说明两个区间没有交集,直接返回-1,因为区间没有链接上
            if (i < nums.size() && nums[i][0] > begin )
            {
                ret = -1;
                break;
            }

			//如果当前已经满足情况就直接break,无需计算了
            if ( end >= L ) 
            	break;
              
        }
        
        if ( ret == -1 || end < L )
            cout<<-1<<endl;
        else cout<<ret<<endl;
    }
    return 0;
}

0

评论区