【华为OD-E卷 -48 观看文艺汇演问题 100分（python、java、c++、js、c）】

【华为OD-E卷 - 观看文艺汇演问题 100分（python、java、c++、js、c）】

题目

为了庆祝中国共产党成立 100 周年，某公园将举行多场文艺表演，很多演出都是同时进行。
一个人只能同时观看一场演出，且不能迟到早退。
由于演出分布在不同的演出场地，所以连续观看的演出最少有 15 分钟的时间间隔。
小明是一个狂热的文艺迷，想观看尽可能多的演出。
现给出演出时间表，请帮小明计算他最多能观看几场演出

输入描述

• 第一行为一个数 N，表示演出场数

1 ≤ N ≤ 1000 接下来 N 行，每行有被空格分割的整数，第一个整数 T 表示演出的开始时间，第二个整数 L 表示演出的持续时间

T 和 L 的单位为分钟 0 ≤ T ≤ 1440 0 < L ≤ 180

输出描述

• 输出最多能观看的演出场数

用例

用例一：

输入：

2
720 120
840 120

输出：

1

用例二：

输入：

2
0 60
90 60

输出：

2

python解法

• 解题思路：
• 问题分析：

该问题需要我们计算出最多可以安排多少个事件，条件是：事件之间至少间隔15分钟。
每个事件由开始时间和持续时间组成，结束时间 = 开始时间 + 持续时间。
我们需要根据结束时间来安排事件，以便最大化选择事件的数量。
关键思路：

贪心算法：从结束时间最早的事件开始选择，每次选择一个事件后，下一次选择的事件必须要在当前选择事件的结束时间之后至少15分钟。
按照事件的结束时间升序排序，逐一选择事件并判断是否满足条件。
具体步骤：

将输入的事件转化为开始时间和结束时间的对。
对事件按结束时间排序，便于选择结束时间最早的事件。
使用贪心策略：遍历排序后的事件，选择结束时间最早且符合时间间隔条件的事件，更新当前已选择事件的结束时间。

class EventScheduler:
    def __init__(self, events):
        # 初始化，处理事件列表，调用_process_events方法将每个事件的结束时间计算出来
        self.events = self._process_events(events)

    def _process_events(self, events):
        # 处理事件，将每个事件的开始时间和结束时间计算出来
        return [[begin, begin + length] for begin, length in events]

    def calculate_max_events(self):
        # 先根据事件的结束时间排序，目的是优先考虑结束时间早的事件
        self.events.sort(key=lambda e: e[1])
        
        # 初始化，第一个事件的结束时间是选择的第一个事件的结束时间
        last_finish_time = self.events[0][1]
        
        # 最初选一个事件
        max_count = 1

        # 从第二个事件开始，遍历所有事件
        for i in range(1, len(self.events)):
            # 如果当前事件的开始时间距离上一个事件的结束时间大于等于15分钟，则可以选择
            if self.events[i][0] - last_finish_time >= 15:
                max_count += 1  # 选择这个事件，最大事件数加1
                last_finish_time = self.events[i][1]  # 更新当前已选择事件的结束时间

        # 返回最多可以安排的事件数量
        return max_count

def main():
    # 输入事件的数量
    num_events = int(input())
    
    # 存储所有事件的开始时间和持续时间
    events = []

    # 读取每个事件的开始时间和持续时间
    for _ in range(num_events):
        begin, length = map(int, input().split())
        events.append([begin, length])

    # 创建事件调度器对象，并计算最多可安排的事件数量
    scheduler = EventScheduler(events)
    print(scheduler.calculate_max_events())  # 输出最大可安排事件数

if __name__ == "__main__":
    # 调用主函数执行
    main()

java解法

• 解题思路
• 问题分析：

我们需要根据给定的多个时间段（每个时间段由开始时间和持续时间给出）来安排最多的电视节目。
关键点是：如果两个节目之间的时间间隔小于15分钟，则不能同时播放。我们需要计算最多可以安排多少个节目。
给定的节目时间段以开始时间和持续时间为输入，我们需要计算每个节目的结束时间。
贪心算法：

我们可以使用贪心策略来解决这个问题：
首先，按照节目的结束时间升序排序，优先选择结束时间较早的节目。
然后，通过遍历排序后的节目的时间段，选择每个结束时间早且与之前选择的节目之间的间隔大于等于15分钟的节目。
贪心选择的原则是每次选择结束时间最早且与前一个节目的结束时间间隔较大的节目，以便为后面的节目腾出更多的时间。
具体步骤：

解析输入并存储每个节目的开始时间和结束时间。
对节目时间段按照结束时间排序。
遍历排序后的节目列表，如果当前节目和之前选择的节目之间的间隔大于等于15分钟，则选择该节目。

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // 创建扫描器来读取输入
        Scanner sc = new Scanner(System.in);
        
        // 读取节目的数量
        int numShows = sc.nextInt();
        
        // 创建二维数组来存储节目时间段的开始和结束时间
        int[][] timeSlots = new int[numShows][2];

        // 读取每个节目的开始时间和持续时间
        for (int i = 0; i < numShows; i++) {
            int start = sc.nextInt();  // 节目的开始时间
            int length = sc.nextInt(); // 节目的持续时间
            timeSlots[i][0] = start;   // 将开始时间存入数组
            timeSlots[i][1] = start + length; // 计算并存储结束时间
        }

        // 调用maxShows方法来计算可以安排的最多节目数量
        System.out.println(maxShows(timeSlots));
    }

    public static int maxShows(int[][] timeSlots) {
        // 按照节目结束时间升序排序
        Arrays.sort(timeSlots, (slot1, slot2) -> Integer.compare(slot1[1], slot2[1]));
        
        // 初始化最多可选节目数为1（第一个节目一定能选）
        int maxShows = 1;
        
        // 记录当前已选节目的结束时间
        int prevEndTime = timeSlots[0][1];

        // 遍历剩余的节目，选择符合条件的节目
        for (int i = 1; i < timeSlots.length; i++) {
            // 如果当前节目的开始时间与上一个节目结束时间的间隔大于等于15分钟，则可以选择当前节目
            if (timeSlots[i][0] - prevEndTime >= 15) {
                maxShows++;  // 可以选择该节目，更新节目数
                prevEndTime = timeSlots[i][1];  // 更新已选节目结束时间
            }
        }

        // 返回可以安排的最大节目数
        return maxShows;
    }
}

C++解法

• 解题思路
• 问题分析：

给定一组时间区间，表示多个活动或节目的开始时间和持续时间。我们需要计算最多可以安排多少个节目，且每个节目之间的时间间隔必须大于等于15分钟。
问题的本质是：如何最大化选择活动，使得每次选择的活动的结束时间和下一个活动的开始时间之间有足够的间隔。
贪心算法：

排序：首先，按活动的结束时间（开始时间 + 持续时间）升序排列。这样，我们可以优先选择结束时间最早的活动。
选择活动：选择第一个活动后，遍历剩下的活动，若当前活动的开始时间距离上一个已选择活动的结束时间至少15分钟，则选择该活动。
解决步骤：

输入活动的开始时间和持续时间，计算每个活动的结束时间。
按结束时间升序排列所有活动。
通过遍历排序后的活动列表，使用贪心策略选择可以安排的活动，计算最大可安排的活动数。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 比较函数：按照活动的结束时间升序排列
bool cmp(const vector<int>& x, const vector<int>& y) {
    return x[1] < y[1];  // x[1]是结束时间，y[1]也是结束时间，按照结束时间进行升序排列
}

int main() {
    int sz;
    cin >> sz;  // 读取活动的数量

    // 创建二维vector，用于存储每个活动的开始时间和结束时间
    vector<vector<int> > rng(sz, vector<int>(2));  

    // 读取每个活动的开始时间和持续时间，并计算结束时间
    for (int i = 0; i < sz; i++) {
        cin >> rng[i][0] >> rng[i][1];   // 读取开始时间和持续时间
        rng[i][1] += rng[i][0];           // 计算结束时间 = 开始时间 + 持续时间
    }

    // 按照结束时间对活动进行升序排序
    sort(rng.begin(), rng.end(), cmp);

    // 选择第一个活动，并记录它的结束时间
    int tmp = rng[0][1];
    int res = 1;  // 初始化已选择的活动数为1，因为第一个活动一定能选择

    // 遍历剩余的活动，按照贪心策略选择可以安排的活动
    for (int i = 1; i < sz; i++) {
        int lft = rng[i][0];  // 当前活动的开始时间
        int rgt = rng[i][1];  // 当前活动的结束时间

        // 如果当前活动的开始时间与上一个已选活动的结束时间间隔至少15分钟
        if (lft - tmp >= 15) {
            res++;         // 可以选择当前活动，已选择活动数加1
            tmp = rgt;     // 更新已选择活动的结束时间
        }
    }

    // 输出可以安排的最大活动数
    cout << res << endl;

    return 0;
}

C解法

• 解题思路

更新中

JS解法

• 解题思路

更新中

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏