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

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为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
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
输出：
1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
用例二：
输入：
2
0 60
90 60
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
输出：
2
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

python解法

输入处理：

输入演出数量 num_performances。
每场演出输入开始时间 start_time 和持续时长 duration，计算每场演出的结束时间 end_time。
将 [start_time, end_time] 添加到 schedule 列表中。
排序日程：

按演出结束时间对 schedule 进行升序排序，贪心策略的核心在于选择尽可能早结束的演出。
选择演出：

初始化计数器 count 为 1，表示至少可以安排第一场演出。
遍历 schedule，判断每场演出的开始时间与上一场演出结束时间的间隔是否大于等于 15 分钟：
如果满足条件，则选择该演出，并更新 last_end_time 为当前演出的结束时间。
输出结果：

返回最多能安排的演出数量

def max_performances(schedule):
    """
    计算最多能安排的演出数量，保证每场演出之间至少有15分钟的间隔
    :param schedule: List[List[int]]，每场演出的开始和结束时间
    :return: int，最多能安排的演出数量
    """
    # 按结束时间升序排序，便于使用贪心算法
    schedule.sort(key=lambda x: x[1])

    # 初始化计数器，选择第一场演出
    count = 1
    # 记录第一场演出的结束时间
    last_end_time = schedule[0][1]

    # 遍历后续演出
    for i in range(1, len(schedule)):
        # 检查当前演出的开始时间与上一场演出结束时间的间隔是否 >= 15
        if schedule[i][0] - last_end_time >= 15:
            count += 1  # 选择当前演出
            last_end_time = schedule[i][1]  # 更新最后的结束时间

    return count

def main():
    """
    主函数，负责处理输入并调用 max_performances 函数计算结果
    """
    # 输入演出的数量
    num_performances = int(input())
    schedule = []

    # 输入每场演出的开始时间和持续时间，计算其结束时间
    for _ in range(num_performances):
        start_time, duration = map(int, input().split())
        # 将每场演出的 [开始时间, 结束时间] 添加到列表
        schedule.append([start_time, start_time + duration])

    # 输出最多能安排的演出数量
    print(max_performances(schedule))

if __name__ == "__main__":
    main()

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

java解法

每场演出有开始时间和持续时间。
两场相邻演出之间至少需要 15分钟 的间隔时间。
算法采用贪心策略：

按演出结束时间升序排序，优先安排结束时间较早的演出。
遍历排序后的日程表，依次选择满足条件的演出：
当前演出开始时间与上一场已选演出的结束时间间隔至少为15分钟。
返回选择的演出总数。

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

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入演出数量
        int numPerformances = scanner.nextInt();
        // 初始化演出日程数组，每场演出用 [开始时间, 结束时间] 表示
        int[][] schedule = new int[numPerformances][2];

        // 输入每场演出的开始时间和持续时间，并计算结束时间
        for (int i = 0; i < numPerformances; i++) {
            int startTime = scanner.nextInt(); // 开始时间
            int duration = scanner.nextInt(); // 持续时间
            schedule[i][0] = startTime; // 设置开始时间
            schedule[i][1] = startTime + duration; // 计算并设置结束时间
        }

        // 输出最大可安排的演出数量
        System.out.println(maxPerformances(schedule));
    }

    /**
     * 计算最多可以安排的演出数量
     * @param schedule 演出日程数组，每项为 [开始时间, 结束时间]
     * @return 最大可安排的演出数量
     */
    public static int maxPerformances(int[][] schedule) {
        // 按演出结束时间升序排序
        Arrays.sort(schedule, (a, b) -> Integer.compare(a[1], b[1]));

        // 初始化计数器，选择第一个演出
        int count = 1;
        // 记录已选演出的最后结束时间
        int lastEndTime = schedule[0][1];

        // 遍历排序后的日程，从第二场演出开始
        for (int i = 1; i < schedule.length; i++) {
            // 如果当前演出的开始时间与上一次选定的结束时间间隔 >= 15 分钟
            if (schedule[i][0] - lastEndTime >= 15) {
                count++; // 选择当前演出
                lastEndTime = schedule[i][1]; // 更新最后结束时间
            }
        }

        return count; // 返回总共选择的演出数量
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

具体思路如下：

输入区间：

输入包含 sz 个区间，每个区间由开始时间 start 和持续时间 duration 构成。
计算每个区间的结束时间 end = start + duration。
按结束时间排序：

使用贪心策略，优先选择结束时间较早的区间，以便为后续区间留出更多选择空间。
选择区间：

遍历排序后的区间，依次判断当前区间的开始时间与上一个选中区间的结束时间是否满足间隔时间 >= 15分钟。
如果满足条件，则选择该区间并更新上一次选中区间的结束时间。
输出结果：

最终输出选中区间的数量

#include 
#include 
#include 

using namespace std;

// 比较函数，用于按区间的结束时间升序排序
bool cmp(const vector<int>& x, const vector<int>& y) {
    return x[1] < y[1]; // 按结束时间排序
}

int main() {
    int sz; // 区间数量
    cin >> sz;

    // 定义二维向量存储区间，每个区间包含开始时间和结束时间
    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;         // 初始化结果，至少可以选择一个区间

    // 遍历剩余区间，按照贪心策略选择满足条件的区间
    for (int i = 1; i < sz; i++) {
        int lft = rng[i][0]; // 当前区间的开始时间
        int rgt = rng[i][1]; // 当前区间的结束时间

        // 判断当前区间是否与上一个选中区间间隔 >= 15 分钟
        if (lft - tmp >= 15) {
            res++;    // 选择当前区间
            tmp = rgt; // 更新最后选中区间的结束时间
        }
    }

    // 输出结果：最多能选择的区间数量
    cout << res << endl;

    return 0;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

JS解法

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

注意：

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

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/145052326"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！