前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >区间调度问题

区间调度问题

作者头像
杨鹏伟
发布2020-09-14 11:24:53
3670
发布2020-09-14 11:24:53
举报
文章被收录于专栏:ypwypw

题意:有n项工作,每项工作分别在si时间开始,在ti时间结束。对于每项工作,你都可以选择参与与否。如果选择了参与,那么自始至终都必须全程参与。此外,参与工作的时间段不能重合。然后问你的目标是参与尽可能多的工作,那么你最多能参与多少项工作?

思路:这种题目我们很容易想到贪心的方案,但问题的重点是我们该如何执行贪心。我们在可选的工作中,每次选择结束时间最早的工作。

代码语言:javascript
复制
#include<bits/stdc++.h>

using namespace std;
const int maxn = 100000;

pair<int,int> itv[maxn];

void solve(){
	for(int i=0;i<n;i++){
		itv.first = t[i];
		itv.second = s[i];
	}
	sort(itv,itv+n);
	
	int ans = 0,t = 0;
	
	for(int i=0;i<n;i++){
		if(t < itv.second) ans++,t=itv.first;
	}
	cout<<ans<<endl;
	
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-09-11 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档