返回目录

题目描述

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

它的大概原理是这样的：

1. 在一天24小时内，可以注册每个App的允许使用时段
2. 一个时间段只能使用一个App
3. App有优先级，数值越高，优先级越高。注册使用时段时，如果高优先级的App时间和低优先级的时段有冲突，则系统会自动注销低优先级的时段，如果App的优先级相同，则后添加的App不能注册。

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

输入描述

第一行表示注册的App数量 N（N ≤ 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. 定义App类：首先，我们定义了一个App类来存储每个App的相关信息，包括名称、优先级、起始时间和结束时间。
2. 时间转换： 将时间从"小时:分钟"格式的字符串转换为以分钟为单位的整数。
3. 处理注册的App：创建另一个ArrayList来存储注册的App。对于每个App，我们检查它的时间段是否与已注册App的时间段重叠。如果有重叠，我们比较它们的优先级。如果当前App的优先级高于已注册的App，则注销低优先级的App。否则，跳过当前App。这样确保了在任何给定时间，只有最高优先级的App被注册。
4. 查询特定时间的App：读取时间，然后遍历注册的App列表，找到在该时间活跃的App（即查询时间在App的起始时间和结束时间之间）。将此App的名称存储在变量 appAtTime中。

总结：核心思想是首先读取App信息并转换时间格式，然后在注册阶段处理时间冲突和优先级问题，最后根据查询时间确定哪个App是活跃的，并输出该App的名称。

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 convert_time(time_str):
    hours, minutes = map(int, time_str.split(':'))
    return hours * 60 + minutes

n = int(input())  # 读取App数量

apps = []  # 创建App列表，用于存储所有App
for _ in range(n):
    # 循环读取每个App的信息，并创建App对象添加到列表中
    app_name, app_priority, start_time_str, end_time_str = input().split()
    app_start_time = convert_time(start_time_str)
    app_end_time = convert_time(end_time_str)
    apps.append(App(app_name, int(app_priority), app_start_time, app_end_time))

query_time_str = input()
query_time = convert_time(query_time_str)  # 读取查询时间，并转换为分钟
app_at_time = "NA"  # 初始化查询时间对应的App名称为"NA"

registered_apps = []  # 创建已注册App列表
for app in apps:
    if app.start_time >= app.end_time:
        continue  # 如果起始时间不小于结束时间，则跳过

    # 遍历已注册的App列表，检查时间冲突
    for registered in reversed(registered_apps):
        # 如果存在时间冲突
        if max(app.start_time, registered.start_time) < min(app.end_time, registered.end_time):
            # 如果当前App的优先级高于已注册App的优先级
            if app.priority > registered.priority:
                registered_apps.remove(registered)  # 注销低优先级的App
            else:
                continue  # 如果优先级不高，继续检查下一个已注册App

    # 将当前App添加到已注册App列表中
    registered_apps.append(app)

# 遍历已注册App列表，找到查询时间对应的App
for app in registered_apps:
    if query_time >= app.start_time and query_time < app.end_time:
        app_at_time = app.name  # 更新查询时间对应的App名称
        break  # 找到后退出循环

print(app_at_time)  # 输出查询时间对应的App名称

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义App结构体，用于存储App的相关信息
typedef struct {
    char name[50]; // App名称
    int priority; // App优先级
    int start_time; // App允许使用的起始时间（以分钟为单位）
    int end_time; // App允许使用的结束时间（以分钟为单位）
} App;

// 时间转换函数，将时间字符串转换为以分钟为单位的整数
int convert_time(const char* time) {
    int hours, minutes;
    sscanf(time, "%d:%d", &hours, &minutes); // 将时间字符串按照":"分割并转换为小时和分钟
    return hours * 60 + minutes; // 将小时和分钟转换为分钟
}

int main() {
    int n; // 读取App数量
    scanf("%d", &n);

    App *apps = (App*)malloc(n * sizeof(App)); // 创建App数组，用于存储所有App
    for (int i = 0; i < n; i++) {
        // 循环读取每个App的信息，并创建App对象添加到数组中
        char appName[50];
        int appPriority, appStartTime, appEndTime;
        char startTimeStr[10], endTimeStr[10];
        scanf("%s %d %s %s", appName, &appPriority, startTimeStr, endTimeStr);
        appStartTime = convert_time(startTimeStr);
        appEndTime = convert_time(endTimeStr);
        strcpy(apps[i].name, appName);
        apps[i].priority = appPriority;
        apps[i].start_time = appStartTime;
        apps[i].end_time = appEndTime;
    }

    char queryTimeStr[10];
    scanf("%s", queryTimeStr);
    int queryTime = convert_time(queryTimeStr); // 读取查询时间，并转换为分钟
    char appAtTime[50] = "NA"; // 初始化查询时间对应的App名称为"NA"

    App *registeredApps = (App*)malloc(n * sizeof(App)); // 创建已注册App数组
    int numRegisteredApps = 0; // 记录已注册App的数量

    for (int i = 0; i < n; i++) {
        App app = apps[i];
        if (app.start_time >= app.end_time) continue; // 如果起始时间不小于结束时间，则跳过

        int conflict = 0;
        // 遍历已注册的App数组，检查时间冲突
        for (int j = 0; j < numRegisteredApps; j++) {
            App registered = registeredApps[j];
            // 如果存在时间冲突
            if (app.start_time < registered.end_time && app.end_time > registered.start_time) {
                // 如果当前App的优先级高于已注册App的优先级
                if (app.priority > registered.priority) {
                    // 注销低优先级的App
                    for (int k = j; k < numRegisteredApps - 1; k++) {
                        registeredApps[k] = registeredApps[k + 1];
                    }
                    numRegisteredApps--;
                    j--; // 因为删除了一个元素，所以需要将索引减一
                } else {
                    conflict = 1;
                    break;
                }
            }
        }

        if (!conflict) {
            // 将当前App添加到已注册App数组中
            registeredApps[numRegisteredApps] = app;
            numRegisteredApps++;
        }
    }

    // 遍历已注册App数组，找到查询时间对应的App
    for (int i = 0; i < numRegisteredApps; i++) {
        App app = registeredApps[i];
        if (queryTime >= app.start_time && queryTime < app.end_time) {
            strcpy(appAtTime, app.name); // 更新查询时间对应的App名称
            break; // 找到后退出循环
        }
    }

    printf("%s\n", appAtTime); // 输出查询时间对应的App名称

    free(apps);
    free(registeredApps);

    return 0;
}

java算法源码

import java.util.Scanner;

// 定义App类，用于存储App的相关信息
class App {
    String name; // App名称
    int priority; // App优先级
    int startTime; // App允许使用的起始时间（以分钟为单位）
    int endTime; // App允许使用的结束时间（以分钟为单位）

    // 构造函数
    public App(String name, int priority, int startTime, int endTime) {
        this.name = name;
        this.priority = priority;
        this.startTime = startTime;
        this.endTime = endTime;
    }
}

public class Main {
    // 时间转换函数，将时间字符串转换为以分钟为单位的整数
    static int convertTime(String time) {
        String[] parts = time.split(":");
        int hours = Integer.parseInt(parts[0]);
        int minutes = Integer.parseInt(parts[1]);
        return hours * 60 + minutes;
    }

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

        int n = scanner.nextInt(); // 读取App数量
        scanner.nextLine(); // 消耗换行符

        App[] apps = new App[n]; // 创建App数组，用于存储所有App
        for (int i = 0; i < n; i++) {
            // 循环读取每个App的信息，并创建App对象添加到数组中
            String[] appInfo = scanner.nextLine().split(" ");
            String appName = appInfo[0];
            int appPriority = Integer.parseInt(appInfo[1]);
            int appStartTime = convertTime(appInfo[2]);
            int appEndTime = convertTime(appInfo[3]);
            apps[i] = new App(appName, appPriority, appStartTime, appEndTime);
        }

        String queryTimeStr = scanner.nextLine();
        int queryTime = convertTime(queryTimeStr); // 读取查询时间，并转换为分钟
        String appAtTime = "NA"; // 初始化查询时间对应的App名称为"NA"

        App[] registeredApps = new App[n]; // 创建已注册App数组
        int numRegisteredApps = 0; // 记录已注册App的数量

        for (int i = 0; i < n; i++) {
            App app = apps[i];
            if (app.startTime >= app.endTime) continue; // 如果起始时间不小于结束时间，则跳过

            boolean conflict = false;
            // 遍历已注册的App数组，检查时间冲突
            for (int j = 0; j < numRegisteredApps; j++) {
                App registered = registeredApps[j];
                // 如果存在时间冲突
                if (app.startTime < registered.endTime && app.endTime > registered.startTime) {
                    // 如果当前App的优先级高于已注册App的优先级
                    if (app.priority > registered.priority) {
                        // 注销低优先级的App
                        for (int k = j; k < numRegisteredApps - 1; k++) {
                            registeredApps[k] = registeredApps[k + 1];
                        }
                        numRegisteredApps--;
                        j--; // 因为删除了一个元素，所以需要将索引减一
                    } else {
                        conflict = true;
                        break;
                    }
                }
            }

            if (!conflict) {
                // 将当前App添加到已注册App数组中
                registeredApps[numRegisteredApps] = app;
                numRegisteredApps++;
            }
        }

        // 遍历已注册App数组，找到查询时间对应的App
        for (int i = 0; i < numRegisteredApps; i++) {
            App app = registeredApps[i];
            if (queryTime >= app.startTime && queryTime < app.endTime) {
                appAtTime = app.name; // 更新查询时间对应的App名称
                break; // 找到后退出循环
            }
        }

        System.out.println(appAtTime); // 输出查询时间对应的App名称
    }
}