文档章节

1133 不重叠的线段 (贪心算法,最大区间不重合问题)

o
 osc_1ee7cxmx
发布于 2018/08/06 21:19
字数 259
阅读 7
收藏 0

精选30+云产品,助力企业轻松上云!>>>

X轴上有N条线段,每条线段有1个起点S和终点E。最多能够选出多少条互不重叠的线段。(注:起点或终点重叠,不算重叠)。
 
例如:[1 5][2 3][3 6],可以选[2 3][3 6],这2条线段互不重叠。
Input
第1行:1个数N,线段的数量(2 <= N <= 10000)
第2 - N + 1行:每行2个数,线段的起点和终点(-10^9 <= S,E <= 10^9)
Output
输出最多可以选择的线段数量。
Input示例
3
1 5
2 3
3 6
Output示例
2


代码如下:
#include<cstdio>
#include<algorithm>
#define MAXN 100010
using namespace std;
struct node
{
 int l, r;
};
bool cmp(node a, node b)
{
 return a.r < b.r;
}
node num[MAXN];
int main()
{
 int n;
 while (scanf("%d", &n) != EOF)
 {
  for (int i = 0; i < n; i++)
   scanf("%d%d", &num[i].l, &num[i].r);
  sort(num, num + n, cmp);
  int ans = 0;
  if (n>0)
  {
   ans = 1;
   int temp = num[0].r;
   for (int i = 0; i < n;i++)
   if (num[i].l >= temp)
   {
    temp = num[i].r;
    ans++;
   }
  }
  printf("%d\n", ans);
 }
 return 0;
}
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

在Bash脚本中,如果发生某种情况,如何退出整个脚本?

问题: I'm writing a script in Bash to test some code. 我正在Bash中编写脚本来测试一些代码。 However, it seems silly to run the tests if compiling the code fails in the first pl......

技术盛宴
47分钟前
18
0
Windows安装Python+OpenCV

1、更新PyCharm中pip来源,使用清华和阿里云:https://pypi.tuna.tsinghua.edu.cn/simple/ http://mirrors.aliyun.com/pypi/simple/ 2、PyCharm查看已安装packets,添加新的安装包,从pip云端...

极客行
今天
17
0
tomcat8配置虚拟目录,实现一个tomcat运行两个项目, tomcat配置URL不区分大小写

<?xml version="1.0" encoding="UTF-8"?><!-- Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements. See the NOTICE file distri......

青峰Jun19er
今天
19
0
HBase和MySQL存储方式的差别?或者说是,行存储和列存储的区别?

HBase借鉴列存储的思想,但是最底层依然是依靠键值对来存储数据,HBase为非关系型数据库 而MySQL则是行存储,MySQL为关系型数据库 写过程 行存储因为数据是连续的,所以只需要进行追加即可;...

其乐m
今天
25
0
一个老程序员在互联网寒冬下的感悟

1. 你千万不要认为学习技术就可以换来稳定的生活和高的薪水待遇,你更不要认为那些从事市场开发,跑腿的人,没有前途。 不清楚你是不是知道,咱们中国有相当大的一部分软件公司,他们的软件开...

北柠Java
今天
39
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部