| 题目名称 | 2298. [HZOI 2015]简单的区间问题 |
|---|---|
| 输入输出 | get_pos.in/out |
| 难度等级 | ★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Aglove
于2016-05-10加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：8， 提交：13， 通过率：61.54% | ||||
 rewine |
100 | 0.006 s | 0.46 MiB | C++ |
 神利·代目 |
100 | 0.027 s | 0.60 MiB | C++ |
|
ymxbiss |
100 | 0.030 s | 0.60 MiB | C++ |
 YGOI_真神名曰驴蛋蛋 |
100 | 0.066 s | 8.68 MiB | C++ |
 Aglove |
100 | 0.214 s | 1.84 MiB | C++ |
 assassain |
100 | 0.230 s | 0.87 MiB | C++ |
 0 |
100 | 0.249 s | 0.44 MiB | C++ |
 stdafx.h |
100 | 0.274 s | 0.45 MiB | C++ |
|
assassain |
80 | 3.259 s | 0.89 MiB | C++ |
 splitspaces |
60 | 0.043 s | 57.41 MiB | C++ |
| 关于 简单的区间问题 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
有O(n)的算法。。。。。。
| ||||
|
题解戳http://www.cnblogs.com/joyouth/p/5476772.html
Aglove
2016-05-10 10:04
1楼
| ||||
【题目描述】
这是一个简单的区间问题
给定你n个区间，然后有两个问题
第一个问题要求你选出最多的区间，使得选出的区间任意两个都没有重叠部分
第二个问题要求你给所有区间分组，使得每个组的区间任意两个都没有重叠部分，求最少的组数
【输入格式】
第一行输入n表示有n个区间
以下n行每行输入两个L，R，表示一个[L,R]的区间
n<=10000,L,R<=10^8，数据保证L<=R
【输出格式】
输出两行
第一行表示第一问的答案
第二行表示第二问的答案
【样例输入】
3
1 2
2 3
3 4
【样例输出】
2
2
【提示】
关于"没有重叠部分的例子";
1、[2,3]和[1,4]具有重叠部分
2、[1,2]和[2,3]具有重叠部分
3、[1,2]和[3,4]不具有重叠部分