首页 > 其他分享 >区间覆盖

区间覆盖

时间:2022-12-10 11:46:38浏览次数:49  
标签:覆盖 int ed st 端点 区间 最优

题目连接:https://www.acwing.com/problem/content/909/

题目描述

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t],请你选择尽量少的区间,将指定线段区间完全覆盖。
输出最少区间数,如果无法完全覆盖则输出 −1。

输入描述

第一行包含两个整数 s 和 t,表示给定线段区间的两个端点。
第二行包含整数 N,表示给定区间数。
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。

输出描述

输出一个整数,表示所需最少区间数。
如果无解,则输出 −1。
1≤N≤105
−109≤ai≤bi≤109
−109≤s≤t≤109

示例

输入

1 5
3
-1 3
2 4
3 5

输出

2

分析

算法过程

记待覆盖区间为[st,ed]。

本题算法过程如下:

  1. 将每个区间按照左端点从小到大进行排序。
  2. 从前往后枚举区间,选择覆盖st且右端点最大的区间,用该区间的右端点更新st,重复本步骤直到完成整个区间的覆盖。

证明

将该算法得到的结果与最优解进行对比。记算法的到的方案为A,最优解为B。

以第一个被选中的区间为例,A选出的区间的右端点一定大于等于B选出区间的右端点,因此可以用A的第一个区间替换B的第一个区间,B的正确性不变,区间数量不变,因此新B依然是最优解。

此时A与B第一个区间完全一样,重复上面的步骤对第二个、第三各区间····进行同样的操作替换最优解中的区间,即可在保持区间数量不变和正确性的前提下将最优解变为A。

证毕。这是局部最优解与全局最优解保持一致的典型贪心算法。

AC代码


#include <iostream>
#include <algorithm>
using namespace std;

typedef pair<int, int> P;
const int N = 1e5 + 10;
int n;
P a[N];
int st, ed;

int main()
{
	cin >> st >> ed >> n;
	for (int i = 0; i < n; i++)
	{
		int l, r;
		cin >> l >> r;
		a[i].first = l;
		a[i].second = r;
	}
	sort(a, a + n);
	int res = 0;
	bool success = false;
	for (int i = 0; i < n; i++)
	{
		int j = i, r = -1e9 - 10;
		while (j < n && a[j].first <= st)
		{
			r = max(r, a[j].second);
			j++;
		}
		j--;
		if (r < st)
		{
			res = -1;
			break;
		}
		res++;
		st = r;
		if (r >= ed)
		{
			success = true;
			break;
		}
		i = j;
	}
	if (success)
		cout << res << endl;
	else
		cout << -1 << endl;
	return 0;
}

标签:覆盖,int,ed,st,端点,区间,最优
From: https://www.cnblogs.com/kongaobo/p/16971322.html

相关文章

  • 区间分组
    题目连接:https://www.acwing.com/problem/content/908/题目描述给定N个闭区间[ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组......
  • Git强制覆盖master
    场景由于公司的项目中,有一个开发分支(这里假设dev​)是一个严重偏离master​,需要我去强制覆盖master​。问题这个场景带来了两个问题:​master​是受保护不能强推​dev......
  • 力扣436(java&python)-寻找右区间(中等)
    题目:给你一个区间数组intervals,其中 intervals[i]=[starti,endi],且每个 starti都不同。区间i的右侧区间可以记作区间j,并满足startj >=endi,且start......
  • CTF新手入门(变量覆盖)
    变量覆盖顾名思义:可以改一个值去覆盖这个变量,我们可以利用它做些什么一般会考:Extract() Parse_str() 什么是Extract()?我帮你百度了一下:PHPextract()函数从数......
  • git强制远程更新覆盖本地修改
    git强制远程更新覆盖本地修改 gitpull时出现冲突放弃本地修改,使远程库内容强制覆盖本地代码 1.gitfetch--all //从远程拉取最新的代码不merge2.gitreset......
  • [研究中] 固定半径最少圆覆盖问题/固定数量最小半径覆盖问题
    一、固定半径最少圆覆盖问题背景:二维坐标轴中,给出n个点以及每个点的坐标(坐标为浮点型),和一个长度m(m为浮点型),求至少需要多个半径为m的圆可以把所有点覆盖住输入:第一行输入n......
  • git pull 强制覆盖本地文件
    “gitpull”强制覆盖本地文件放弃本地修改,使用服务器代码覆盖本地的Git命令如下:gitfetch--allgitreset--hardorigin/mastergitpull上面代码使用master分......
  • poj1651 Multiplication Puzzle--区间dp
    原题链接:​​http://poj.org/problem?id=1651​​题意:给出N个数,每次从中抽出一个数(第一和最后一个不能抽),每次的得分为抽出的数与相邻两个数的乘积,直到只剩下首尾两个数为......
  • hdu3632 A Captivating Match--区间dp
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=3632​​题意:n个人比赛,每个人一个价值v[i],相邻两人a,b比赛,输的人淘汰,最后剩下的那个人的价值最大可以是多少?分析:相......
  • hdu4632 Palindrome subsequence--区间dp
    原题链接:​​http://acm.hdu.edu.cn/showproblem.php?pid=4632​​题意:求一个字符串所有子序列是回文的个数,注意子序列是这样的情况:原串abcde,子串abd。注意与子串含义不同。......