1643 线段覆盖 3

1643 线段覆盖 3

时间限制: 2 s

空间限制: 256000 KB

题目等级 : 黄金 Gold

题目描述 Description

在一个数轴上有n条线段,现要选取其中k条线段使得这k条线段两两没有重合部分(端点可以重合),问最大的k为多少。

输入描述 Input Description

输入格式

输入文件的第1行为一个正整数n,下面n行每行2个数字ai,bi,描述每条线段。

输出描述 Output Description

输出格式

  输出文件仅包括1个整数,为k的最大值

样例输入 Sample Input

3

0 2

2 4

1 3

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

数据范围

对于20%的数据,n≤10;

对于50%的数据,n≤1000;

对于70%的数据,n≤100000;

对于100%的数据,n≤1000000,0≤ai<bi≤1000000。

分类标签 Tags 点此展开

我们首先按他的结束顺序排序

然后比较每一个与他前面已放置的是否冲突就可以

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 struct node
 7 {
 8     int x;
 9     int y;
10 }a[1000001];
11 int num=1;
12 int comp(const node & a,const node & b)
13 {
14     return a.y<b.y;
15 }
16 int main()
17 {
18     int n;
19     scanf("%d",&n);
20     for(int i=1;i<=n;i++)
21     {
22         scanf("%d%d",&a[num].x,&a[num].y);
23         num++;
24     }
25     sort(a+1,a+num,comp);
26     int tot=0;
27     int last=a[1].y;
28     for(int i=1;i<=num-1;i++)
29     {
30         if(a[i+1].x>=last)
31         {
32             tot++;
33             last=a[i+1].y;
34         }
35     }
36     printf("%d",tot+1);
37     return 0;
38 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏DannyHoo的专栏

Block

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u010105969/article/details/...

13120
来自专栏从流域到海域

《笨办法学Python》 第32课手记

《笨办法学Python》 第32课手记 本节课讲for循环和list,list里类似于c中的数组,但有区别很大。C语言中的数组是数据类型相同的值的集合,list...

21790
来自专栏大闲人柴毛毛

稳扎稳打JavaScript(一)——作用域链内存模型

几个概念 在开始之前,先了解几个概念。 1.1. 作用域 作用域是指当前正在执行的代码能够访问到变量的范围; 每个函数都有各自的作用域,存储函数所有的局部变量...

48980
来自专栏技术栈大杂烩

Python: 作用域(scope) 和 LEGB

不管在什么编程语言, 都有作用域这个概念.作用域控制在它范围内代码的生存周期, 包括名字和实体的绑定.

12630
来自专栏日常分享

Spring 学习笔记(七)—— 切入点表达式

  语法结构:   execution(   方法修饰符  方法返回值  方法所属类 匹配方法名 (  方法中的形参表 )  方法申明抛出的异常  )

6310
来自专栏蜕变

Python 数据类型

Python主要数据类型包括list(列表)、tuple(元组)、dict(字典)和set(集合)等对象,下面逐一介绍这些Python数据类型。

9500
来自专栏九彩拼盘的叨叨叨

JavaScript 字符串练习题

如果对字符串的 API 不是很熟悉,可查阅 W3School JavaScript String API。

9710
来自专栏程序员互动联盟

【编程基础】C语言复合赋值运算符

在C语言的赋值中有一种特殊的赋值运算符,就是复合赋值运算符。复合赋值运算符就是在赋值符“=”之前加上其它二目运算符可构成。比如大家可能最常看到这样的语句: n ...

49860
来自专栏java 成神之路

JAVA对象在JVM中内存分配

391120
来自专栏JavaEdge

青铜到王者 ,快速提升你 Go语言的段位! "狗"语言实战(二)- 基础语法1 变量定义

15140

扫码关注云+社区

领取腾讯云代金券