手机App防沉迷系统 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

题目描述

智能手机方便了我们生活的同时，也侵占了我们不少的时间。“手机Ap防沉迷系统” 能够让我们每天合理的规划手机App使用时间，在正确的时间做正确的事。

它的大概原理是这样的:

1、在一天24小时内，可注册每个App的允许使时段;

2、一个时间段只能使用一个APP， 不能在同时注册App2 和 App3;

3、App有优先级，数值越高，优先级越高。注册使用时段时，如果高优先级的App时间和低优先级的时段有冲突，则系统会自动注销低优先级的时段；

如果App的优先级相同，则后添加的App不能注册。

请编程实现，根据输入数据注册App，并根据输入的时间点，返回时间点注册的App名称，如果该时间点没有注册任何App，请返回字符串“NA"。

输入描述

第一行表示注册的App数N

第二部分包括N 行，每行表示一条App注册数据

最后一行输入一个时间点，程序即返回注册点可App

2
App1 1 09:00 10:00
App2 2 11:00 11:30
09:30
数据说明如下
1、N行注册数据以空格分隔，四项数依次表示: App名称、优先级、起始时间，结束时间
2.优先级1-5，数字值越大，优先级越高
3、时间格式HH:MM，小时和分钟都是两位，不足两位前面补0
4.起始时间需小于结束时间，否则注册不上
5.注册信息中的时间段包含起始时间点，不包含结束时间点

输出描述

输出一个字符串，表示App名称，或NA表示空闲时间。

示例1

输入：
1
App1 1 09:00 10:00
09:30

输出：
App1

说明：
App1注册在9点到10点间，9点半可用的应用名是App1

示例2

输入：
2
App1 1 09:00 10:00
App2 2 09:10 09:30
09:20

输出：
App2

说明：
ApP1和App2的时段有冲突，App2优先级高,注册App2之后，App1自动注销，因此输出App2

示例3

输入：
2
App1 1 09:00 10:00
App2 2 09:10 09:30
09:50

输出：
NA

题解

这是一个模拟题，需要按照题目描述的规则模拟注册过程，并在给定时间点找到注册的App。

程序的解题思路和关键步骤：

1. 定义一个App类，用于表示应用程序对象，包括应用程序名称、优先级、开始时间和结束时间。同时，在App类中实现一个方法判断两个应用程序对象是否有时间重叠。
2. 编写convertToMinutes方法，将时间字符串转换为分钟表示的整数。
3. 编写convertToApp方法，将输入的字符串转换为应用程序对象。
4. 通过读取输入，获取应用程序的数量，以及每个应用程序的注册信息。将注册信息转换为App对象，并根据题目规则进行注册。如果新注册的应用程序与已有的应用程序有时间重叠，根据优先级判断是否需要注销低优先级的应用程序。
5. 读取给定的时间点，将其转换为分钟表示的整数。
6. 遍历已注册的应用程序列表，找到包含给定时间的应用程序。
7. 输出结果。

该程序使用了类的封装和集合的操作，通过遍历和比较，实现了应用程序的注册和冲突处理。最后，根据给定时间点找到相应的应用程序并输出结果。

时间复杂度：O(N^2)，其中N为应用程序的数量。在每次注册应用程序时，都需要遍历已有的应用程序列表，判断是否有时间重叠。

空间复杂度：O(N)，存储了已注册的应用程序列表。

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class App {
    String name;        // 应用程序名称
    int priority;       // 优先级
    int startTime;      // 开始时间（以分钟为单位）
    int endTime;        // 结束时间（以分钟为单位）

    // 构造函数，用于初始化应用程序对象
    public App(String name, int priority, int startTime, int endTime) {
        this.name = name;
        this.priority = priority;
        this.startTime = startTime;
        this.endTime = endTime;
    }

    // 判断当前应用程序与另一个应用程序是否有时间重叠
    public boolean hasOverlap(App other) {
        return this.startTime < other.endTime && other.startTime < this.endTime;
    }
}
/**
 * @author code5bug
 */
class Main {
    // 将时间字符串转换为分钟表示的整数
    public static int convertToMinutes(String time) {
        String[] arr = time.split(":");
        int hour = Integer.parseInt(arr[0]);
        int minute = Integer.parseInt(arr[1]);
        return hour * 60 + minute;
    }

    // 将输入字符串转换为应用程序对象
    public static App convertToApp(String input) {
        String[] arr = input.split(" ");
        String name = arr[0];
        int priority = Integer.parseInt(arr[1]);
        int startTime = convertToMinutes(arr[2]);
        int endTime = convertToMinutes(arr[3]);
        return new App(name, priority, startTime, endTime);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int numApps = scanner.nextInt();   // 输入应用程序的数量
        scanner.nextLine(); // 消耗掉换行符

        // 存储应用程序对象的数组
        List<App> apps = new ArrayList<>();

        // 读取并转换应用程序信息
        for (int i = 0; i < numApps; i++) {
            String input = scanner.nextLine();
            App app = convertToApp(input);

            // 如果开始时间大于结束时间，则忽略该应用程序
            if (app.startTime > app.endTime) {
                continue;
            }

            // 与当前应用程序时间重叠的应用程序
            List<App> overlappingApps = new ArrayList<>();
            int maxPriority = -1;
            for (int j = 0; j < apps.size(); j++) {
                App tmp = apps.get(j);
                if (app.hasOverlap(tmp)) {
                    overlappingApps.add(tmp);
                    maxPriority = Math.max(maxPriority, tmp.priority);
                }
            }

            // 当前App与已有的App的优先级相同，则后添加的App不能注册
            // 高优先级的App时间和低优先级的时段有冲突，则系统会自动注销低