【华为机试】2023年真题B卷（python）-观看文艺汇演-计算演出场次

一、题目

题目描述：

一个人只能同时观看一场演出，且不能迟到早退，由于演出分布在不同的演出场地，所以连续观看的演出最少有15分钟的时间间隔，小明是一个狂热的文艺迷，想观看尽可能多的演出， 现给出演出时间表，请帮小明计算他最多能观看几场演出。 第一行为一个数N，表示演出场数，1<=N<=1000，接下来N行，每行两个空格分割的整数，第一个整数T表示演出的开始时间，第二个整数L表示演出的持续时间，T和L的单位为分钟，0<=T<=1440,0<L<=100.
输出最多能观看的演出场数。?

二、示例

示例1：
输入：
2
720 120
840 120
输出：
1
示例2：
输入：
2
0 60
90 60
输出：
2

三、要求

时间限制：C/C++ 1秒，其他语言 2秒
空间限制：C/C++262144K，其他语言524288K

四、解题思路

我们可以使用贪心算法来解决这个问题。首先，我们将演出时间表按照开始时间从小到大进行排序。然后，我们从第一场演出开始，依次遍历演出时间表。对于每一场演出，我们检查是否存在足够的时间间隔来观看下一场演出。如果存在足够的时间间隔，我们将观看的演出场数加一，并更新当前观看的结束时间。如果不存在足够的时间间隔，我们跳过当前演出，继续检查下一场演出。最后，返回观看的演出场数作为结果。

五、参考代码?

# -*- coding: utf-8 -*-
'''
@File    :   2023-B-观看文艺汇演-计算演出场次.py
@Time    :   2023/12/29 18:40:26
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''

# import os
# import re
# import sys
# import copy
# import math
# import queue
# import functools
# from queue import Queue
# from collections import Counter, defaultdict

def calculate_max_shows(N):
    
    shows = []  # 演出时间表

    # 获取演出时间表
    for _ in range(N):
        T, L = map(int, input().split())
        shows.append((T, L))

    shows.sort()  # 按开始时间排序

    max_shows = 0  # 最多能观看的演出场数
    end_time = -15  # 当前观看的演出的结束时间，初始化为-15分钟

    for show in shows:
        start_time, duration = show

        if start_time >= end_time + 15:  # 存在至少15分钟的时间间隔
            max_shows += 1
            end_time = start_time + duration

    print(max_shows)  # 输出最多能观看的演出场数

N = int(input())  # 演出场数
calculate_max_shows(N)