手机App防沉迷系统 - 华为OD统一考试

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\le 100)$

第二部分包括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时间和低优先级的时段有冲突，则系统会自动注销低优先级的时段（ 当前App优先级低于其他冲突的App 则也不能注册）
            if (app.priority <= maxPriority) {
                continue;
            } else {
                // 将之前已经注册优先级较低有时段有冲突的App 注销掉
                apps.removeAll(overlappingApps);
            }

            // 注册当前 App
            apps.add(app);
        }


        int givenTime = convertToMinutes(scanner.nextLine());  // 给定时间
        String answer = "NA";

        // 遍历结果列表，找到包含给定时间的应用程序
        for (App app : apps) {
            if (app.startTime <= givenTime && givenTime < app.endTime) {
                answer = app.name;
                break;
            }
        }

        System.out.println(answer);  // 输出结果
    }
}

Python

class App:
    def __init__(self, name, priority, start_time, end_time):
        self.name = name
        self.priority = priority
        self.start_time = start_time
        self.end_time = end_time

    def has_overlap(self, other):
        return self.start_time < other.end_time and other.start_time < self.end_time

# 将时间字符串转换为分钟表示的整数
def convert_to_minutes(time_str):
    hour, minute = map(int, time_str.split(":"))
    return hour * 60 + minute

# 将输入字符串转换为应用程序对象
def convert_to_app(input_str):
    parts = input_str.split()
    name = parts[0]
    priority = int(parts[1])
    start_time = convert_to_minutes(parts[2])
    end_time = convert_to_minutes(parts[3])
    return App(name, priority, start_time, end_time)

if __name__ == "__main__":
    num_apps = int(input())
    apps = []

    # 读取并转换应用程序信息
    for _ in range(num_apps):
        app_input = input()
        app = convert_to_app(app_input)

        # 如果开始时间大于结束时间，则忽略该应用程序
        if app.start_time > app.end_time:
            continue

        overlapping_apps = []
        max_priority = -1

        # 与当前应用程序时间重叠的应用程序
        for tmp in apps:
            if app.has_overlap(tmp):
                overlapping_apps.append(tmp)
                max_priority = max(max_priority, tmp.priority)

        # 当前App与已有的App的优先级相同，则后添加的App不能注册
        # 高优先级的App时间和低优先级的时段有冲突，则系统会自动注销低优先级的时段
        if app.priority <= max_priority:
            continue
        else:
            # 将之前已经注册优先级较低有时段有冲突的App 注销掉
            for tmp in overlapping_apps:
                apps.remove(tmp)

        # 注册当前 App
        apps.append(app)

    given_time = convert_to_minutes(input())  # 给定时间
    answer = "NA"

    # 遍历结果列表，找到包含给定时间的应用程序
    for app in apps:
        if app.start_time <= given_time < app.end_time:
            answer = app.name
            break

    print(answer)  # 输出结果

C++

#include <bits/stdc++.h>

using namespace std;

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

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

    // 判断当前应用程序与另一个应用程序是否有时间重叠
    bool hasOverlap(const App& other) const {
        return this->startTime < other.endTime && other.startTime < this->endTime;
    }
};

// 将时间字符串转换为分钟表示的整数
int convertToMinutes(const string& time) {
    size_t pos = time.find(":");
    int hour = stoi(time.substr(0, pos));
    int minute = stoi(time.substr(pos + 1));
    return hour * 60 + minute;
}

// 将输入字符串转换为应用程序对象
App convertToApp(const string& input) {
    size_t pos1 = input.find(" ");
    size_t pos2 = input.find(" ", pos1 + 1);
    size_t pos3 = input.find(" ", pos2 + 1);

    string name = input.substr(0, pos1);
    int priority = stoi(input.substr(pos1 + 1, pos2 - pos1 - 1));
    int startTime = convertToMinutes(input.substr(pos2 + 1, pos3 - pos2 - 1));
    int endTime = convertToMinutes(input.substr(pos3 + 1));

    return App(name, priority, startTime, endTime);
}

int main() {
    int numApps;
    cin >> numApps;   // 输入应用程序的数量
    cin.ignore(); // 消耗掉换行符

    // 存储应用程序对象的数组
    vector<App> apps;

    // 读取并转换应用程序信息
    for (int i = 0; i < numApps; i++) {
        string input;
        getline(cin, input);
        App app = convertToApp(input);

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

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

        // 当前App与已有的App的优先级相同，则后添加的App不能注册
        // 高优先级的App时间和低优先级的时段有冲突，则系统会自动注销低优先级的时段（ 当前App优先级低于其他冲突的App 则也不能注册）
        if (app.priority <= maxPriority) {
            continue;
        } else {
            // 将之前已经注册优先级较低有时段有冲突的App 注销掉
            for(int j = overlappingApps.size() - 1; j >= 0; j--){
                apps.erase(apps.begin() + overlappingApps[j]);
            }
        }

        // 注册当前 App
        apps.push_back(app);
    }

    int givenTime;
    string givenTimeString;
    getline(cin, givenTimeString);
    givenTime = convertToMinutes(givenTimeString);  // 给定时间
    string answer = "NA";

    // 遍历结果列表，找到包含给定时间的应用程序
    for (const App& app : apps) {
        if (app.startTime <= givenTime && givenTime < app.endTime) {
            answer = app.name;
            break;
        }
    }

    cout << answer << endl;  // 输出结果

    return 0;
}

????华为OD机试面试交流群（每日真题分享）： 加V时备注“华为od加群”

🙏整理题解不易， 如果有帮助到您，请给点个赞 ???? 和收藏 ?，让更多的人看到。🙏🙏🙏