首页 > 其他分享 >每日一题-区间覆盖

每日一题-区间覆盖

时间:2022-11-09 22:01:37浏览次数:42  
标签:cout 覆盖 int 端点 区间 一题 las

区间覆盖

        sort(a.begin(), a.end());
	int ans = 0, las = s;
	for (int i = 0; i < n; ++i) {
		int j = i;
		int r = -2e9;
		while (j < n and a[j].first <= las) {
			r = max(r, a[j].second);
			j ++;
		}
		if (r >= las) {
			ans ++, las = r;
		} else {
			cout << -1;
			return 0;
		}
		if (las >= t) {
		    break;
		}
		i = j - 1;
	}
	las >= t ? cout << ans << '\n' : cout << -1;

问题简述

有若干备选区间,问能覆盖目标线段的最少区间。

贪心

对区间按左端点排序,对于当前已覆盖区间的右端点(初值为线段左端点)P,选取能覆盖P右端点最大的的区间,且将P更新为这个右端点, O(n)。

标签:cout,覆盖,int,端点,区间,一题,las
From: https://www.cnblogs.com/whose-dream/p/16875325.html

相关文章

  • 每日一题-叠罗汉的牛
    叠罗汉的牛 sort(a.begin(),a.end(),[](constauto&A,constauto&B){ returnA.first+A.second<B.first+B.second; }); intsum=0,ans=-2e9; ......
  • 76.最小覆盖子串
    给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。注意:对于 t 中......
  • HDU 1255 覆盖的面积
    ProblemDescription给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积. Input输入数据的第一行是一个正整数T(1<=T<=100),代表测试......
  • 367页资料详解企业数字化转型,覆盖多行业!附下载
    ​据工信部网站11月8日消息,为助力中小企业数字化转型,工业和信息化部组织相关单位共同研究制定了《中小企业数字化水平评测指标(2022年版)》(以下简称《评测指标》)。《指南》明......
  • 基础算法篇——区间合并
    基础算法篇——区间合并本次我们介绍基础算法中的区间合并,我们会从下面几个角度来介绍:区间合并区间合并我们这次的目的很简单:快速高效的完成区间合并任务区间合......
  • 每日一题之Vue数据劫持原理是什么?
    什么是数据劫持?定义:数据劫持,指的是在访问或者修改对象的某个属性时,通过一段代码拦截这个行为,进行额外的操作或者修改返回结果。简单地说,就是当我们触发函数的时候动......
  • 使用前缀和数组解决"区间和查询"问题
    本文已收录到 GitHub·AndroidFamily,有Android进阶知识体系,欢迎Star。技术和职场问题,请关注公众号[彭旭锐]进Android面试交流群。前言大家好,我是小彭。今......
  • 2022-11-08 Acwing每日一题
    本系列所有题目均为Acwing课的内容,发表博客既是为了学习总结,加深自己的印象,同时也是为了以后回过头来看时,不会感叹虚度光阴罢了,因此如果出现错误,欢迎大家能够指出错误,我......
  • 45th ICPC昆明 C.Cities(区间dp)
    题目链接Description有n个点,每个点有自己的颜色(并且每种颜色出现次数不超过15次),每次操作可以把一段连续且颜色相同的点染成任意一种颜色,求把所有点染成相同颜色的最小操......
  • 树形DP之点覆盖问题
    什么是点覆盖问题?就是在树上选几个点,覆盖(一个点可以覆盖其相连的边或与其距离不超过\(d\)的点,根据题意具体分析)一些点或边,求最小代价。例题战略游戏题意一棵无根树,......