51Nod 1428 活动安排问题

时间:2022-08-26 13:29:23

51Nod   1428  活动安排问题

Link: http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428

基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题
51Nod 1428 活动安排问题有若干个活动,第i个开始时间和结束时间是[Si,fi),同一个教室安排的活动之间不能交叠,求要安排所有活动,最少需要几个教室? 
Input
第一行一个正整数n (n <= 10000)代表活动的个数。
第二行到第(n + 1)行包含n个开始时间和结束时间。
开始时间严格小于结束时间,并且时间都是非负整数,小于1000000000
Output
一行包含一个整数表示最少教室的个数。
Input示例
3
1 2
3 4
2 9
Output示例
2

题解:

简单的题目, 排序之后, 放进优先队列中,进行模拟,解决!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 100000 + 5; struct Node{
int r, l;
}nd[maxn];
int n; int cmp(const void *a, const void *b){
Node *aa = (Node *)a;
Node *bb = (Node *)b;
return aa->l - bb->l;
} int main(){
/// freopen("in.txt", "r", stdin); int x, y, p, ans, cur;
while(scanf("%d", &n) != EOF){
for(int i=0; i<n; ++i){
scanf("%d %d", &nd[i].l, &nd[i].r);
}
qsort(nd, n, sizeof(nd[0]), cmp); ans = 1;
priority_queue<int, vector<int>, greater<int>> qt;
qt.push(nd[0].r);
for(int i=1; i<n; ++i){
if(!qt.empty()){
cur = qt.top();
if(nd[i].l >= cur){
qt.pop();
}else{
++ans;
}
qt.push(nd[i].r);
}else{
qt.push(nd[i].r);
}
}
printf("%d\n", ans);
}
return 0;
}

  

51Nod 1428 活动安排问题的更多相关文章

  1. 51nod 1428 活动安排问题&lpar;优先队列&rpar;

    1428 活动安排问题 首先按照开始时间从小到大排序. 其实只要维护一个结束时间的最小堆,每次比较开始时间和堆中最小时间的大小,如果比它大就放入堆中并且时间就要变成当前任务的结束时间, 否则就要新开一 ...

  2. 51nod 1428 活动安排问题 &lpar;贪心&plus;优先队列&rpar;

    来源:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428 首先按照开始时间从小到大排序. 其实只要维护一个结束时间的最 ...

  3. 51Nod:活动安排问题之二(贪心)

    有若干个活动,第i个开始时间和结束时间是[Si,fi),同一个教室安排的活动之间不能交叠,求要安排所有活动,最少需要几个室? 输入 第一行一个正整数n (n <= 10000)代表活动的个数. ...

  4. 51Nod:活动安排问题(区间问题)

    X轴上有N条线段,每条线段有1个起点S和终点E.最多能够选出多少条互不重叠的线段.(注:起点或终点重叠,不算重叠). 例如:[1 5][2 3][3 6],可以选[2 3][3 6],这2条线段互不重 ...

  5. 51nod 1428 贪心

    http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428 1428 活动安排问题 基准时间限制:1 秒 空间限制:13107 ...

  6. 51nod1428 活动安排问题 &lpar;贪心加暴力)

    1428 活动安排问题 基准时间限制:1 秒 空间限制:131072 KB 分值: 10 难度:2级算法题  收藏  关注 有若干个活动,第i个开始时间和结束时间是[Si,fi),同一个教室安排的活动 ...

  7. C语言 活动安排问题

    有若干个活动,第i个开始时间和结束时间是[Si,fi),只有一个教室,活动之间不能交叠,求最多安排多少个活动? #include <stdio.h> #include <stdlib ...

  8. hdu 2037简单贪心--活动安排问题

    活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合,是可以用贪心算法有效求解的很好例子.该问题要求高效地安排一系列争用某一公共资源的活动.贪心算法提供了一个简单.漂亮的方法使得尽可能多的活动 ...

  9. 忙碌的Nova君 (活动安排问题、贪心算法)

    题目描述 理论上,Nova君是个大闲人,但每天还是有一大堆事要干,大作业啦,创新杯啦,游戏啦,出题坑人啦,balabala......然而精力有限,Nova君同一时间只能做一件事,并不能一心二用.假设 ...

随机推荐

  1. &lpar;转&rpar;nginx优化 实现10万并发访问量

    转自http://www.cnblogs.com/pricks/p/3837149.html 一般来说nginx配置文件中对优化比较有作用的为以下几项:worker_processes 8;1 ngi ...

  2. WebService - 怎样提高WebService性能 大数据量网络传输处理

    直接返回DataSet对象 返回DataSet对象用Binary序列化后的字节数组 返回DataSetSurrogate对象用Binary序列化后的字节数组 返回DataSetSurrogate对象用 ...

  3. 数据结构--树状数组&amp&semi;&amp&semi;线段树--基本操作

    随笔目的:方便以后对树状数组(BIT)以及基本线段树的回顾 例题链接:http://acm.hdu.edu.cn/showproblem.php?pid=1166 例题:hdu 1166 敌兵布阵 T ...

  4. Inspector a ProgressBar&lpar;定制属性面板&rpar;

    一.定制进度条 这篇文章主要学习如何在Unity的Inspector中使用ProgressBar 普通属性面板预览 通常我们的属性面板如下 定制属性面板预览 而通过扩展成ProcessBar后 二.内 ...

  5. &lbrack;RMQ&rsqb; &lbrack;线段树&rsqb; POJ 3368 Frequent Values

    一句话,多次查询区间的众数的次数 注意多组数据!!!! RMQ方法: 预处理 i 及其之前相同的数的个数 再倒着预处理出 i 到不是与 a[i] 相等的位置之前的一个位置, 查询时分成相同的一段和不同 ...

  6. oracle的row&lowbar;number&lpar;&rpar;和rownum

    row_number() 函数和rownum的介绍: 1.row_number() 方法的格式: row_number()over([partition by col1] order by col2) ...

  7. HDU 2602 Bone Collector&lpar;01背包裸题&rpar;

    Bone Collector Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) T ...

  8. POJ2947-Widget Factory

    工厂里每件期间的生产时间为3-9天,告诉你有N个器件和M个计划,每个计划都是说明生产1-N号器件的时间,最后问你每件器件的生产时间.或者多解或没有解. 例如样例 2 3 2 MON THU 1 2 3 ...

  9. localStorage的使用记录

    // 存数据 var str = JSON.stringify(back); localStorage.setItem("options", str); // 取数据 var op ...

  10. innodb&lowbar;file&lowbar;per&lowbar;table

    MySQL InnoDB引擎 默认会将所有的数据库InnoDB引擎的表数据存储在一个共享空间中:ibdata1,当增删数据库的时候,ibdata1文件不会自动收缩,单个数据库的备份也将成为问题.通常只 ...