• • 题目描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例：
      • 输出样例：
  • 贪心算法求解
    • 分析
    • 代码
    • 时间复杂度
  • 参考文章

题目传送门

题目描述

给定 NN 个闭区间 [ai,bi][ai,bi] 以及一个线段区间 [s,t][s,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出 ?1?1。

输入格式

第一行包含两个整数 ss 和 tt，表示给定线段区间的两个端点。

第二行包含整数 NN，表示给定区间数。

接下来 NN 行，每行包含两个整数 ai,biai,bi，表示一个区间的两个端点。

输出格式

输出一个整数，表示所需最少区间数。

如果无解，则输出 ?1?1。

数据范围

1≤N≤1051≤N≤105,
?109≤ai≤bi≤109?109≤ai≤bi≤109,
?109≤s≤t≤109?109≤s≤t≤109

输入样例：

1 5
3
-1 3
2 4
3 5

输出样例：

2

贪心算法求解

分析

1. 将所有线段按左端点排序
2. 选择能够覆盖当前st的所有线段中右端点最大的
   1. 如果没有则说明不能覆盖
   2. 有的话将当前st更新为该最大右端点
3. 如果选择了当前最大右端点之后，该右端点大于ed，说明覆盖完成，直接break

代码

#include
#include
#include
#include
using namespace std;
typedef long long LL; 
typedef pair PII;
const int N = 100010;
const int INF = 1e9 + 7;
vector ranges;

int st, ed;
int n;

bool cmp(PII a, PII b)
{
	return a.first < b.first;
}

int main()
{
	scanf("%d%d", &st, &ed);
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		ranges.push_back({l,r});	
	}	
	sort(ranges.begin(),  ranges.end(), cmp);
	
	bool flag = false;
	int res = 0;
	
	for(int i = 0; i < n; i++)
	{
		int j = i, r = -INF;
		// 用双指针找出所有左端点在st之前的线段的右端点的最大值 
		while(j < n && ranges[j].first <= st)
		{
			r = max(r, ranges[j].second);
			j++;
		}
		
		if(r < st) break; //如果没有能覆盖当前st的线段，说明不能覆盖
		
		
		res ++; // 选择这条右端最靠右的线段 
		if(r >= ed)
		{
			flag = true;
			break;
		} 
			
		st = r; 
		i = j - 1;
	}
	if(flag) cout << res << endl;
	else 	 cout << -1 << endl;
	
	return 0;
}

时间复杂度

\(O(nlogn)\)

参考文章

https://www.acwing.com/solution/content/16980/