题目描述设有个n活动的集合E={1,2,..,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间s_i 和一个结束时间f_i,且s_i < f_is 。如果选择了活动i,则它在时间区间 [ s_i ,
展开全文
本题为贪心区间
求最大可容纳活动数
贪心在于排序
本题与普通合并区间最大的区别是筛选区间
并不是简单将区间合并求最长区间
而是保证活动数最大
那么就要求每个区间尽可能的小
求出开始时间相同区间中结束最快的区间
所以要对数据按第一个数进行从小到大的排序
并筛去开始时间在这段时间内的区间
后统计还剩几个
展开全文
选择不相交区间 问题描述： 数轴上有n条线段，选取其中k条线段使得这k条线段两两没有重合部分，问k最大为多少。 输入描述:第一行为一个正整数n；在接下来的n行中，每行有2个数ai，bi描述每条线段。 输出描述:输出一个整数，为k的最大值。 思路： 区间x完全包含y，选y 按照bi从小到大排序，从第
展开全文
本题可以转化成最多不重叠区间覆盖问题，要想使最多，就要对右区间从小到大排序，然后要对左区间进行特判，找出第一个左边界大于等于上一个区间的右边界的区间作为下一个区间。
#include<bits/stdc++.h>
using namespace std;
int n;
const int
展开全文
活动安排：贪心思想，区间合并的一种转换，首先你需要对左区间从小到大进行排序，当左区间相等时右区间从小到大排序为最优解，初始答案为1，左端点为最小的左端点，右端点为对应右端点，当右端点大于等于此时的左端点答案加一，更新此时的右端点为现在的右端点，当右端点大于此时的右端点此时答案不变但当前集合最优解为现
展开全文
活动安排
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
in
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
