ural 1203. Scientific Conference(动态规划)
2024-09-10 20:01:38
1203. Scientific Conference
Time limit: 1.0 second Memory limit: 64 MB
Functioning of a scientific conference is usually divided into several simultaneous sections. For example, there may be a section on parallel computing, a section on visualization, a section on data compression, and so on.
Obviously, simultaneous work of several sections is necessary in order to reduce the time for scientific program of the conference and to have more time for the banquet, tea-drinking, and informal discussions. However, it is possible that interesting reports are given simultaneously at different sections.
A participant has written out the time-table of all the reports which are interesting for him. He asks you to determine the maximal number of reports he will be able to attend.
Input
The first line contains the number 1 ≤ N ≤ 100000 of interesting reports. Each of the next N lines contains two integers Ts and Te separated with a space (1 ≤ Ts < Te ≤ 30000). These numbers are the times a corresponding report starts and ends. Time is measured in minutes from the beginning of the conference.
Output
You should output the maximal number of reports which the participant can attend. The participant can attend no two reports simultaneously and any two reports he attends must be separated by at least one minute. For example, if a report ends at 15, the next report which can be attended must begin at 16 or later.
Sample
input | output |
---|---|
5 |
3 |
#include <cstring>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
struct node
{
int x,y;
} p[];
int flag[];
int cmp(node a,node b)
{
if(a.x == b.x)
return a.y < b.y;
else
return a.x < b.x;
}
int main()
{
freopen("1.txt","r",stdin);
int n,i,j,ans,maxz,top;
scanf("%d",&n);
for(i =; i < n; i ++)
{
scanf("%d%d",&p[i].x,&p[i].y);
}
memset(flag,-,sizeof(flag));
sort(p,p+n,cmp);
ans=;
flag[] = p[].y;
top = ;
for(i =;i<n;i++)
{
maxz = ;
for(j=top;j>=;j--)
{
if(p[i].x>flag[j])
{
maxz=j;
break;
}
}
if(flag[maxz+]==-)
{
flag[maxz+] = p[i].y;
top ++;
}
else
flag[maxz+] = min(flag[maxz+],p[i].y);
}
printf("%d\n",top);
}
最新文章
- 构建通用的 React 和 Node 应用
- hdu-5493 Queue(二分+树状数组)
- Lua游戏脚本语言入门(一)
- Codeforces Round #205 (Div. 2) : D
- css 权威指南笔记( 五)结构和层叠之三种样式来源
- .net如何后台批量删除
- 3. JavaScript 数据类型
- DotNetCore跨平台~Moq框架实现模拟测试
- 常用css样式颜色值: 64位真彩和256位值
- centos7服务器配置nuxt部署环境
- hdfs性能调优(cloudera)
- sha256_transform
- WPS生成文章目录
- 八、UIViewController们之间的协作——Segue
- java StringBuilder和StringBuffer 用法
- Oracle group by
- JMeter学习(十七)JMeter测试MongoDB(转载)
- Delphi下IOCP开源框架:DIOCP 成功应用案例分享
- C++调用C代码的两种方式
- java 正则表达式获得html字符串中<;img src>;中的src中的url地址
热门文章
- dplyr 数据操作 常用函数(2)
- C# 语言规范_版本5.0 (第9章 命名空间)
- php笔记(八)PHP类与对象之抽象类
- springmvc集成aop记录操作日志
- web.xml Attribute ";xmlns"; was already specified for element ";web-app";
- python 学习 [day8]class成员
- MySql-授权,使远程主机能够访问自己的数据库
- jdbc_servlet基础增删改分页2(userinfo表的)
- python Redis
- Android实现动画循环的方式