华为OD机试 - 计算观看演唱会场次（Java 2023 B卷 200分）

题目描述

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

输入描述

• 第一行为一个数N，表示演出场数，1 <= N <= 1000。
• 接下来N行，每行有两个被空格分割的整数：
  • 第一个整数T表示演出的开始时间，单位为分钟，0 <= T <= 1440。
  • 第二个整数L表示演出的持续时间，单位为分钟，0 <= L <= 100。

输出描述

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

解题思路

这是一个典型的活动选择问题，可以使用贪心算法来解决。具体步骤如下：

1. 计算每场演出的结束时间：根据开始时间和持续时间计算每场演出的结束时间。
2. 按结束时间排序：将所有演出按结束时间从早到晚排序。
3. 选择演出：从最早结束的演出开始选择，每次选择结束后，确保下一场演出的开始时间至少比当前演出的结束时间晚15分钟。

代码实现

Java

import java.util.Arrays;
import java.util.Comparator;public class MaxShows {public static int maxShows(int[][] shows) {// 计算每场演出的结束时间for (int[] show : shows) {show[1] += show[0];}// 按结束时间排序Arrays.sort(shows, Comparator.comparingInt(a -> a[1]));int count = 0;int lastEnd = -15; // 初始化为-15，确保第一场演出可以被选择for (int[] show : shows) {if (show[0] >= lastEnd + 15) {count++;lastEnd = show[1];}}return count;}public static void main(String[] args) {int[][] shows = {{600, 90},{720, 60},{800, 45}};System.out.println(maxShows(shows));}
}

Python

def max_shows(shows):# 计算每场演出的结束时间shows = [[start, start + duration] for start, duration in shows]# 按结束时间排序shows.sort(key=lambda x: x[1])count = 0last_end = -15  # 初始化为-15，确保第一场演出可以被选择for show in shows:if show[0] >= last_end + 15:count += 1last_end = show[1]return countshows = [[600, 90],[720, 60],[800, 45]
]
print(max_shows(shows))

C++

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int maxShows(vector<vector<int>>& shows) {// 计算每场演出的结束时间for (auto& show : shows) {show[1] += show[0];}// 按结束时间排序sort(shows.begin(), shows.end(), [](const vector<int>& a, const vector<int>& b) {return a[1] < b[1];});int count = 0;int lastEnd = -15; // 初始化为-15，确保第一场演出可以被选择for (const auto& show : shows) {if (show[0] >= lastEnd + 15) {count++;lastEnd = show[1];}}return count;
}int main() {vector<vector<int>> shows = {{600, 90},{720, 60},{800, 45}};cout << maxShows(shows) << endl;return 0;
}

JavaScript

function maxShows(shows) {// 计算每场演出的结束时间shows = shows.map(show => [show[0], show[0] + show[1]]);// 按结束时间排序shows.sort((a, b) => a[1] - b[1]);let count = 0;let lastEnd = -15; // 初始化为-15，确保第一场演出可以被选择for (const show of shows) {if (show[0] >= lastEnd + 15) {count++;lastEnd = show[1];}}return count;
}const shows = [[600, 90],[720, 60],[800, 45]
];
console.log(maxShows(shows));

测试用例

测试用例1：

• 输入：

  3
  600 90
  720 60
  800 45
  

• 输出：2
• 说明：小明可以观看第一场和第三场演出。

测试用例2：

• 输入：

  4
  500 120
  600 90
  720 60
  800 45
  

• 输出：2
• 说明：小明可以观看第一场和第三场演出。

总结

通过贪心算法，我们可以有效地解决这个问题。首先计算每场演出的结束时间，然后按结束时间排序，最后选择符合条件的演出。这种方法的时间复杂度为O(n log n)，适用于N <= 1000的规模。