编程介的小学生 2019-11-22 23:40 采纳率: 20.5%
浏览 84

Olympic Games 问题怎么解决的

Problem Description
Mike loves the olympic games. What he hates about olympic games – besides them taking place only once every four years – is that the individual events are scheduled concurrently. That way it is never possible to watch all competitions live. Mike always tries to plan his personal schedule in order to maximize the number of events he can attend to. However, at the end he is never sure whether or not his schedule actually is optimal. Help him!

Given the days and times on which events take place, determine the maximum number of events Mike can watch. Mike never leaves during an event, so it is not possible to partially attend to events.

Input
The input starts with a line containing a single integer n, the number of test cases.
Each test case starts with a line containing an integer 1 <= m <= 50000 that specifies the number of different events. The next m lines describe one event with three integers d, s, e. The event takes place on day d of the olympics, it starts at s and it ends at e, where the times are given in the form hhmm. All events are assumed to conclude the same day they started.

Output
The output for every test case begins with a line containing “Scenario #i:”, where i is the number of the test case counting from 1. Then, output a single line containing the number of events Mike can attend to at most. The time for getting from one event to another can be neglected. Events starting at time t can be scheduled after events ending at t as long as there are no other conflicts. Terminate each test case with an empty line.

Sample Input
2
10
1 1220 1340
2 1155 1220
2 1220 1340
3 1220 1240
1 1200 1320
2 1250 1310
2 1330 1550
3 1030 1130
3 1130 1300
3 1240 1330
3
1 0500 2200
1 0000 0700
1 2000 2359

Sample Output
Scenario #1:
7

Scenario #2:
2

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 求差集那个函数有问题,有无佬可以解决
    • ¥15 【提问】基于Invest的水源涵养
    • ¥20 微信网友居然可以通过vx号找到我绑的手机号
    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题