B - 整数区间

Time Limit: 1000/1000MS (C++/Others) Memory Limit: 65536/65536KB (C++/Others)

Problem Description

一个整数区间[a,b](a < b),是一个从a到b连续整数的集合。
现在给你n个整数区间,编程找出一个集合R,使得n个集合中的每个集合都有2个整数出现在R中,并且这个集合R包含的整数个数最少。

Input

第一行包含整数n(1 <= n <= 10000),表示整数区间的个数。接下来n行,每行包含两个整数a和b(0 <= a < b <= 10000, a < b)。

Output

输出符合条件的集合R中元素的个数。

Sample Input

4
3 6
2 4
0 2
4 7

Sample Output

4

Hint

对于输入样例,我们可以找到集合R{1,2,4,5}和R{1,2,4,6},这里R的元素的个数为4.

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std; const int maxn = 1e5+;
struct Node{
int x, y;
bool operator < (const Node& b) const{ // 按照b的升序排序
return y < b.y;
}
}a[maxn]; int main()
{
int n;
scanf("%d", &n);
for(int i=; i<n; i++)
scanf("%d %d", &a[i].x, &a[i].y); sort(a, a+n);
int t1 = -, t2 = -, cnt = ;
// t1 t2表示当前取的,最大的两个数 其中 t1 < t2 for(int i=; i<n; i++){
bool f1 = (t1 >= a[i].x); // t1是否在当前区间
bool f2 = (t2 >= a[i].x); // t2是否在当前区间 if(f1 && f2) ; // 都在 不处理
else if(!f1 && f2) { // t1不在,t2在, 需要再加一个数,替换掉t1, 贪心的取最大的
t1 = a[i].y;
cnt++; // 多需要一个数
}
else { // t1 t2谁都不在,需要再加两个数,贪心地添加最大的两个数
t1 = a[i].y - ;
t2 = a[i].y;
cnt += ;
}
if(t1 > t2) swap(t1, t2); //保持 t1 < t2
}
printf("%d\n", cnt); return ;
}

最新文章

  1. CYQ.Data V4系列全面开源(2013-08-04)
  2. jquery属性选择器(匹配具有指定属性的元素)
  3. Azure开发者任务之一:解决Azure Storage Emulator初始化失败
  4. 机器学习中的矩阵方法(附录A): 病态矩阵与条件数
  5. PostgreSQL Replication之第十二章 与Postgres-XC一起工作(2)
  6. shell小细节
  7. 字典查找、linq、foreach、yield等几种查找性能对比
  8. linux ---用uniq实现文件的并集和交集
  9. struts2学习笔记(3)——struts2的局部类型转换
  10. leptonica 学习笔记1
  11. java 检查是否是数组 检查是否是空数组 检查数组是否包含某个元素
  12. android开发之调试技巧 分类: android 学习笔记 2015-07-18 21:30 140人阅读 评论(0) 收藏
  13. MySQL数据库配置主从服务器实现双机热备
  14. vue日历控件,自定义选择年月 选择年月日 选择年月日时 选择年月日时分,自定义日期范围
  15. 将地图定位封装为ng指令
  16. [转]Firefox+Burpsuite抓包配置(可抓取https)
  17. 【WP8】MultiBinding
  18. js事件轮询机制
  19. c++ mktime()
  20. 新唐M0 M4系统初始化

热门文章

  1. 《计算机图形学3D》
  2. 关于Ext.js和Ext.Net的杂谈
  3. .Net Core On Liunx 环境搭建之 Docker 容器和Nginx
  4. Hadoop(25)-高可用集群配置,HDFS-HA和YARN-HA
  5. hive 学习系列之七 hive 常用数据清洗函数
  6. python循环,函数
  7. centos7上部署新版 jumpserver 跳板机服务
  8. 最短路径问题 3.Bellman-Ford算法
  9. Spark是什么
  10. kudu是什么