华为OD机试真题---观看文艺汇演问题

发布于：2024-12-18 ⋅ 阅读:(174) ⋅ 点赞:(0)

华为OD机试中的“观看文艺汇演问题”是一道考察算法与数据结构能力的题目。以下是对该题目的详细解析：

一、题目描述

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

二、输入与输出

输入描述：

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

输出描述：

  • 输出一个整数，表示小明最多能观看的演出场数。

三、解题思路

  1. 数据预处理：

    • 读取输入的演出数据，并将其存储在一个合适的数据结构中，如二维数组或列表的列表。
    • 为了方便后续计算，可以将每个演出的结束时间也计算出来并存储，即结束时间=开始时间+持续时间+15（因为需要15分钟的时间间隔）。

  2. 排序：

    • 根据演出的开始时间对演出进行排序。如果开始时间相同，则按照结束时间排序（这是为了在处理相同开始时间的演出时，优先选择结束时间早的演出，以便为后续的演出留出更多的时间间隔）。

  3. 动态规划：

    • 使用一个数组dp来记录到当前演出为止，小明最多能观看的演出场数。
    • 初始化dp[0]=1，表示小明至少可以观看第一场演出。
    • 对于后续的每一场演出i，遍历之前的所有演出j（j<i），如果演出j的结束时间小于等于演出i的开始时间，说明小明可以观看演出i。此时，更新dp[i]=max(dp[i], dp[j]+1)，表示小明在观看完演出j后，还可以观看演出i，从而更新最多能观看的演出场数。

  4. 结果输出：

    • 遍历完所有演出后，dp数组中的最大值即为小明最多能观看的演出场数。

四、示例

输入：

4
10 30
20 40
40 20
60 50

输出：

2

解释：

  • 第一场演出10-40，第二场演出20-60（与第一场有冲突，不能看），第三场演出40-60（与第一场冲突，但与第二场结束时间接近，也不能看），第四场演出60-110（可以看，因为与前一场有15分钟间隔）。所以最多看2场：第一场、第三场（选择另一个不与第一场冲突的短演出，这里为了简化说明选择了一个与第一场结束时间接近但实际不会观看的演出作为示例中的“第三场”，实际计算时应考虑所有可能的演出组合）、第四场。但注意，这里的“第三场”仅用于解释思路，实际计算时并不会真的选择这样一个与第一场结束时间接近的演出，而是会选择在所有可能观看的演出中，满足时间间隔要求且能使得观看场数最多的那场演出。正确的选择可能是跳过第二场和假设的“第三场”，直接观看第一场和第四场（或其他满足条件的组合），从而得到最多观看2场的结果。

（注意：上述示例中的“第三场”是为了解释思路而假设的，实际计算时应忽略此假设，直接根据算法找出满足条件的最多观看场数。）

示例1：
输入：

2
720 120
840 120

输出：

1

示例2：
输入：

2
0 60
90 60

输出：

2

五、代码实现

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

public class WatchPerformances {

    /**
     * 计算最大表演场次
     * 该方法旨在找到在满足一定条件下的最大表演场次，条件是每两个连续表演之间需要有足够的间隔时间
     *
     * @param performances 一个二维数组，其中每个元素表示一个表演，包含两个整数：开始时间和持续时间
     * @return 返回最大表演场次
     */
    public static int maxPerformances(int[][] performances) {
        // 表演的数量
        int n = performances.length;

        // 创建一个二维数组，用于存储每个表演的详细信息，包括开始时间、结束时间（包括15分钟间隔）和持续时间
        int[][] performanceDetails = new int[n][3];
        for (int i = 0; i < n; i++) {
            // 保存表演的开始时间
            performanceDetails[i][0] = performances[i][0];
            // 计算并保存表演的结束时间，包括15分钟的间隔
            performanceDetails[i][1] = performances[i][0] + performances[i][1] + 15;
            // 保存表演的持续时间
            performanceDetails[i][2] = performances[i][1];
        }

        // 根据表演的开始时间进行排序，如果开始时间相同，则根据结束时间排序
        Arrays.sort(performanceDetails, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

        // 初始化动态规划数组，每个表演默认至少可以独立进行一次
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        // 动态规划填表，计算每个表演能够达到的最大表演场次
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // 如果前一个表演的结束时间晚于或等于当前表演的开始时间，则更新当前表演的最大表演场次
                if (performanceDetails[j][1] <= performanceDetails[i][0]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        // 找到dp数组中的最大值，即为最大表演场次
        int maxPerformances = Arrays.stream(dp).max().orElse(0);
        return maxPerformances;
    }

    /**
     * 主函数入口
     * 本函数负责读取输入数据，并调用maxPerformances函数计算最大性能值
     */
    public static void main(String[] args) {
        // 创建Scanner对象以读取输入
        Scanner scanner = new Scanner(System.in);

        // 读取输入的表演数量
        int n = scanner.nextInt();

        // 初始化存储表演数据的二维数组
        int[][] performances = new int[n][2];
        // 遍历读取每个表演的两个指标值
        for (int i = 0; i < n; i++) {
            performances[i][0] = scanner.nextInt();
            performances[i][1] = scanner.nextInt();
        }

        // 调用maxPerformances函数计算并获取最大性能值
        int result = maxPerformances(performances);
        // 输出最大性能值
        System.out.println(result);
    }
}

六、详细运行示例解析

输入数据
4
10 30
20 40
40 20
60 50
运行流程解析

  1. 读取输入

    • 程序首先读取一个整数4，表示有4场演出。
    • 接着，程序读取4行数据，每行包含两个整数，分别表示演出的开始时间和持续时间。

  2. 数据预处理

    • 程序将这些数据存储在二维数组performances中。
    • 然后，程序创建另一个二维数组performanceDetails，用于存储每场演出的详细信息：开始时间、结束时间（包括15分钟间隔）和持续时间。
    • performanceDetails数组被填充如下：
      [
  [10, 45, 30], // 第一场演出：开始时间10，结束时间45（10+30+15），持续时间30
  [20, 65, 40], // 第二场演出：开始时间20，结束时间65（20+40+15），持续时间40
  [40, 65, 20], // 第三场演出：开始时间40，结束时间65（40+20+15，但注意这里会与第二场冲突，实际计算时会考虑时间间隔），持续时间20
  [60, 125, 50] // 第四场演出：开始时间60，结束时间125（60+50+15），持续时间50
]

  3. 排序

    • 程序根据演出的开始时间对performanceDetails数组进行排序。如果开始时间相同，则根据结束时间排序。
    • 在这个例子中，排序后的数组顺序与输入顺序相同，因为开始时间已经是有序的，并且没有开始时间相同的演出。

  4. 动态规划

    • 程序初始化一个动态规划数组dp，长度为演出的数量，每个元素初始化为1，表示每场演出至少可以独自被观看一次。
    • 程序使用两个嵌套的循环来计算dp数组的值。对于每场演出i，它遍历之前的所有演出j，如果演出j的结束时间小于等于演出i的开始时间，则更新dp[i]为dp[j] + 1。
    • 在这个例子中，动态规划的过程如下：
      • 初始化dp为[1, 1, 1, 1]。
      • 对于第一场演出（索引0），没有其他演出可以在它之前，所以dp[0]保持为1。
      • 对于第二场演出（索引1），它不能与第一场演出同时观看（因为开始时间太接近，无法满足15分钟的间隔），所以dp[1]也保持为1。
      • 对于第三场演出（索引2），它同样不能与前面的演出同时观看（因为它的开始时间与第二场演出的结束时间冲突），所以dp[2]也保持为1。
      • 对于第四场演出（索引3），它可以与第一场演出同时观看（因为第一场演出的结束时间是45，第四场演出的开始时间是60，满足15分钟的间隔），所以更新dp[3]为dp[0] + 1 = 2。但是，这里我们需要注意，实际上在遍历过程中，我们应该检查所有可能的组合，而不仅仅是最前面的演出。然而，在这个特定例子中，由于时间上的冲突，只有第一场和第四场演出能够满足条件被同时观看（在不考虑其他未列出的更短演出的情况下）。但正确的动态规划过程会考虑所有可能的组合，并更新dp数组以反映最大可能的观看次数。然而，由于示例数据的限制（特别是没有提供能够插入第一场和第四场之间且满足条件的更短演出），动态规划的结果在这个特定情况下可能看起来有些直观上的误导。在实际应用中，更完整的演出列表可能会产生不同的结果。
      • 实际上，由于第三场演出的开始时间与第二场演出的结束时间完全相同（在这个简化的例子中），并且我们要求连续观看的演出之间有15分钟的间隔，所以第三场演出不能与第二场同时观看，也不能在它之前紧接的任何其他演出之后立即观看（除非有另一个未列出的、在第二场和第三场之间结束的演出）。在这个简化的例子中，我们没有这样的演出，所以第三场演出实际上是无法被计入最大观看次数的（至少在这个特定的输入数据集中）。然而，这个结论是基于当前输入数据的限制；在更一般的情况下，动态规划算法会正确地处理所有可能的观看组合。
      • 正确的动态规划过程应该像这样进行：对于每场演出，检查所有之前的演出，看看是否有可能在不违反15分钟间隔规则的情况下观看它们。在这个例子中，由于时间上的紧密安排和缺乏能够填补间隔的更短演出，只有第一场和第四场（或者可能还有其他未列出的、满足条件的组合）能够被计入最大观看次数。
      • 重要的是要理解，这个简化的例子并没有展示动态规划算法的全部能力；在更复杂的场景中，算法会正确地处理所有可能的观看组合和约束条件。
    • 注意：上述解释中关于第三场演出的部分是基于当前输入数据的特定限制和简化假设。在更一般的情况下（即有更完整的演出列表和可能的观看组合时），动态规划算法会正确地计算出最大观看次数。

  5. 输出结果

    • 最后，程序找到dp数组中的最大值，即最大观看次数，并打印出来。
    • 在这个例子中，由于输入数据的限制和上述解释中的原因，输出可能是2（表示最多可以观看两场演出：第一场和第四场）。然而，这个结论是基于当前输入数据的；在更一般的情况下，动态规划算法会根据完整的演出列表和约束条件计算出正确的最大观看次数。

七、注意事项

  • 在实际应用中，可能会有更多的演出和更复杂的观看约束条件。动态规划算法能够处理这些情况，并计算出正确的最大观看次数。
  • 上述解释中关于第三场演出的部分是基于当前输入数据的特定限制和简化假设。在更一般的情况下，动态规划算法会正确地处理所有可能的观看组合和约束条件。
  • 输入数据的准确性和完整性对于正确计算最大观看次数至关重要。在实际应用中，应该确保输入数据是完整且准确的。
  • 在处理时间间隔时，要确保连续观看的演出之间有至少15分钟的间隔。
  • 在使用动态规划时，要注意更新dp数组的方式，确保每次都能得到最多能观看的演出场数。

通过以上步骤，可以高效地解决华为OD机试中的“观看文艺汇演问题”。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布