OpenJudge

4144:畜栏保留问题

总时间限制:
1000ms
内存限制:
65536kB
描述

农场有N头牛,每头牛会在一个特定的时间区间[A, B](包括AB)在畜栏里挤奶,且一个畜栏里同时只能有一头牛在挤奶。现在农场主希望知道最少几个畜栏能满足上述要求,并要求给出每头牛被安排的方案。对于多种可行方案,主要输出一种即可。

输入
输入的第一行包含一个整数N(1 ≤ N ≤ 50, 000),表示有N牛头;接下来N行每行包含两个数,分别表示这头牛的挤奶时间[Ai, Bi](1 ≤ A≤ B ≤ 1, 000, 000)。
输出
输出的第一行包含一个整数,表示最少需要的畜栏数;接下来N行,第i+1行描述了第i头牛所被分配的畜栏编号(从1开始)。
样例输入
5
1 10
2 4
3 6
5 8
4 7
样例输出
4
1
2
3
2
4
来源
http://poj.org/problem?id=3190
全局题号
12066
添加于
2016-10-26
提交次数
334
尝试人数
77
通过人数
35
您的评价 很水 简单 一般 较难 变态
  • 标签(多个标签用空格分隔):
  • 常用标签:
    递归   动态规划   贪心   搜索   枚举   模拟   数学   字符串处理   几何   高精度计算   图论  

共有6人评分

50.0%
16.7%
0.0%
0.0%
33.3%

已有的标签

高精度计算(2) 动态规划(2) 图论(2) 贪心(2) 搜索(2)