题面描述

在智能手机的“App防沉迷系统”中，用户可以注册多个App的使用时段。系统有以下规则：

1. 时段注册：用户可以在一天24小时内为每个App注册允许的使用时段。
2. 时段冲突：一个时间段内只能使用一个App，不能同时使用多个App。
3. 优先级处理：
   • 每个App有一个优先级，数值越高优先级越高。
   • 当高优先级的App注册时段与低优先级的App时段冲突时，系统会自动注销低优先级的App的时段。
   • 如果两个App的优先级相同，后注册的App无法覆盖先注册的App。
4. 多时段注册：一个App可以在一天内注册多个时段。

给定多个App的注册信息和一个查询时间点，要求输出该时间点正在使用的App名称。如果没有任何App在该时间点注册使用，则输出“NA”。

思路

为了实现上述规则，我们可以采用以下步骤：

1. 时间转换：将时间格式“HH:MM”转换为分钟数，方便比较和处理。例如，“09:30”转换为570分钟。
2. 时间线模拟：建立一个长度为1440（24小时×60分钟）的时间线数组，每个元素表示对应分钟使用的App及其优先级。
3. 注册处理：
   • 按照输入的注册顺序依次处理每个App的注册时段。
   • 对于每个App的每一个注册时段，将该时段内的每一分钟进行检查：
     • 如果该分钟尚未被其他App占用，则直接分配给当前App。
     • 如果该分钟已经被其他App占用，则比较优先级：
       • 如果当前App的优先级更高，覆盖原有的App。
       • 如果优先级相同或更低，保持原有的App不变。
4. 查询处理：将查询时间点转换为分钟数，查找时间线数组对应分钟的App名称。如果没有App占用该分钟，则输出“NA”。

这种方法通过时间线数组模拟一天的24小时，确保了时段冲突和优先级规则的正确处理。

cpp

#include <bits/stdc++.h>
using namespace std;

class Application {
public:
    string appName;      // 应用名称
    int appPriority;     // 应用优先级
    int startMinute;     // 开始时间（分钟）
    int endMinute;       // 结束时间（分钟）

    Application(string name, int priority, int startTime, int endTime) 
        : appName(std::move(name)), appPriority(priority),
          startMinute(startTime), endMinute(endTime) {};
};

int convertTime(string &timeStr) {
    // 时间格式 HH:MM，小时和分钟都是两位，不足两位前面补0
    stringstream ss(timeStr);

    string hours;
    getline(ss, hours, ':');

    string minutes;
    getline(ss, minutes, ':');

    return stoi(hours) * 60 + stoi(minutes);
}

string getRegisteredApp(vector<Application> &apps, int queryTime) {
    // 记录已注册的应用
    vector<Application> registeredApps;

    for (const auto &app : apps) {
        // 起始时间 >= 结束时间，则注册失败
        if (app.startMinute >= app.endMinute) continue;

        // 记录被注销的应用的索引
        vector<int> toBeDeletedIdxs;

        bool cannotRegister = false;

        // 比较正在注册的应用和已注册的所有应用
        for (int j = 0; j < registeredApps.size(); j++) {
            Application registeredApp = registeredApps[j];

            // 两个应用的注册时间无冲突，则继续比较下一个已注册应用
            if (registeredApp.startMinute >= app.endMinute || app.startMinute >= registeredApp.endMinute) {
                continue;
            }

            // 如果有冲突，比较优先级
            if (app.appPriority > registeredApp.appPriority) {
                // 记录需要注销的已注册应用的索引
                toBeDeletedIdxs.emplace_back(j);
            } else {
                // 当前应用优先级低或相等，无法注册，终止比较
                cannotRegister = true;
            }
        }

        if (cannotRegister) {
            continue;
        }

        // 反向删除已记录的应用索引，避免索引变化
        for (int j = toBeDeletedIdxs.size() - 1; j >= 0; j--) {
            int deleteIdx = toBeDeletedIdxs[j];
            registeredApps.erase(registeredApps.begin() + deleteIdx);
        }

        // 注册当前应用
        registeredApps.emplace_back(app);
    }

    string result = "NA";

    // 注册成功的应用时间段互不冲突，因此查询时间只会对应一个应用
    for (const auto &app : registeredApps) {
        if (queryTime >= app.startMinute && queryTime < app.endMinute) {
            result = app.appName;
            break;
        }
    }

    return result;
}

int main() {
    int numApps;
    cin >> numApps;

    // 需要注册的应用
    vector<Application> apps;
    for (int i = 0; i < numApps; i++) {
        string name;
        int priority;
        string startTime;
        string endTime;

        cin >> name >> priority >> startTime >> endTime;

        apps.emplace_back(name, priority, convertTime(startTime), convertTime(endTime));
    }

    // 需要查询的时间点
    string queryTime;
    cin >> queryTime;

    cout << getRegisteredApp(apps, convertTime(queryTime)) << endl;

    return 0;
}

python

class Application:
    def __init__(self, app_name, app_priority, start_time, end_time):
        self.app_name = app_name          # 应用名称
        self.app_priority = app_priority   # 应用优先级
        self.start_time = start_time       # 开始时间（分钟）
        self.end_time = end_time           # 结束时间（分钟）


def convert(time_str):
    # 时间格式 HH:MM，小时和分钟都是两位，不足两位前面补0
    hours, minutes = map(int, time_str.split(":"))
    return hours * 60 + minutes


# 输入获取
num_apps = int(input())

# 需要注册的应用
apps = []
for _ in range(num_apps):
    app_name, app_priority, start_time, end_time = input().split(" ")
    apps.append(Application(app_name, int(app_priority), convert(start_time), convert(end_time)))

# 需要查询的时间点
query_time = convert(input())


# 算法入口
def get_result():
    registered_apps = []

    for app in apps:
        # 起始时间>=结束时间，则注册不上
        if app.start_time >= app.end_time:
            continue

        # 记录已注册的应用中被注销的应用的位置
        to_be_deleted_idx = []

        cannot_register = False

        # 比较正在注册的应用和它前面完成注册的所有已注册应用
        for j in range(len(registered_apps)):
            registered_app = registered_apps[j]

            # 两个应用的注册时间无冲突，则继续和下一个已注册应用比较
            if registered_app.start_time >= app.end_time or app.start_time >= registered_app.end_time:
                continue

            # 两个应用的注册时间有冲突，则比较优先级
            if app.app_priority > registered_app.app_priority:
                # 记录需要注销的已注册应用的索引
                to_be_deleted_idx.append(j)
            else:
                # 当前应用的优先级低于或等于已注册应用的优先级，无法注册，终止比较
                cannot_register = True
                break

        # 如果当前应用无法注册，则终止比较
        if cannot_register:
            continue

        # idxs中索引是升序的，采用倒序删除
        to_be_deleted_idx.reverse()
        for idx in to_be_deleted_idx:
            registered_apps.pop(idx)

        registered_apps.append(app)

    result = "NA"

    # 注册成功的应用时间段互不冲突，因此查询时间只会对应一个应用
    for registered_app in registered_apps:
        if registered_app.start_time <= query_time < registered_app.end_time:
            result = registered_app.app_name
            break

    return result


# 算法调用
print(get_result())

java

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

public class Main {
    static class Application {
        String appName;       // 应用名称
        int appPriority;      // 应用优先级
        int startMinute;      // 开始时间（分钟）
        int endMinute;        // 结束时间（分钟）

        public Application(String name, int priority, int startTime, int endTime) {
            this.appName = name;
            this.appPriority = priority;
            this.startMinute = startTime;
            this.endMinute = endTime;
        }
    }

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

        int numApps = sc.nextInt();

        // 需要注册的应用
        ArrayList<Application> apps = new ArrayList<>();
        for (int i = 0; i < numApps; i++) {
            apps.add(new Application(sc.next(), sc.nextInt(), convert(sc.next()), convert(sc.next())));
        }

        // 需要查询的时间点
        int queryTime = convert(sc.next());

        System.out.println(getResult(apps, queryTime));
    }

    public static String getResult(ArrayList<Application> apps, int queryTime) {
        // 记录已注册的应用
        ArrayList<Application> registeredApps = new ArrayList<>();

        outer:
        for (Application app : apps) {
            // 起始时间 >= 结束时间，则注册不上
            if (app.startMinute >= app.endMinute) continue;

            // 记录被注销的已注册应用的索引
            ArrayList<Integer> toBeDeletedIdxs = new ArrayList<>();

            // 比较正在注册的应用和它前面已注册的所有应用
            for (int j = 0; j < registeredApps.size(); j++) {
                Application registeredApp = registeredApps.get(j);

                // 两个应用的注册时间无冲突，则继续比较下一个已注册应用
                if (registeredApp.startMinute >= app.endMinute || app.startMinute >= registeredApp.endMinute) continue;

                // 两个应用的注册时间有冲突，则比较优先级
                if (app.appPriority > registeredApp.appPriority) {
                    // 记录需要注销的已注册应用的索引
                    toBeDeletedIdxs.add(j);
                } else {
                    // 当前应用优先级低于或等于已注册应用的优先级，无法注册，终止比较
                    continue outer;
                }
            }

            // 反向删除被记录的索引
            for (int j = toBeDeletedIdxs.size() - 1; j >= 0; j--) {
                int deleteIdx = toBeDeletedIdxs.get(j);
                registeredApps.remove(deleteIdx);
            }

            registeredApps.add(app);
        }

        String result = "NA";

        // 注册成功的应用时间段互不冲突，因此查询时间只会对应一个应用
        for (Application registeredApp : registeredApps) {
            if (queryTime >= registeredApp.startMinute && queryTime < registeredApp.endMinute) {
                result = registeredApp.appName;
                break;
            }
        }

        return result;
    }

    public static int convert(String time) {
        // 时间格式 HH:MM，小时和分钟都是两位，不足两位前面补0
        String[] timeParts = time.split(":");

        String hours = timeParts[0];
        String minutes = timeParts[1];
        return Integer.parseInt(hours) * 60 + Integer.parseInt(minutes);
    }
}

题目内容

智能手机方便了我们生活的同时，也侵占了我们不少的时间。

“手机$App$防沉迷系统”能够让我们每天合理地规划手机$App$使用时间，在正确的时间做正确的事。

它的大概原理是这样的：

1.在一天24小时内，可以注册每个$App$的允许使用时段

2.一个时间段只能使用一个$App$，举例说明：不能同时在$9:00-10:00$注册$App2$和$App3$

3.$App$有优先级，数值越高，优先级越高。注册使用时段时，如果高优先级的$App$时间和低优先级的时段有冲突，则系统会自动注销低优先级的时段，如果$App$的优先级相同，则后添加的$App$不能注册。

举例1：

(1) 注册$App3$前

(2)$App3$注册时段和$App2$有冲突

(3) $App3$优先级高，系统接受$App3$的注册，自动注销$App2$的注册

举例2：

(1) 注册$App4$

(2) $App4$和$App2$及$App3$都有冲突，优先级比$App2$高，但比$App3$低，这种场景下$App4$注册不上，最终的注册效果如下

4.一个$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$表示空闲时间

备注

• 用例保证时间都介于 $00:00 - 24:00$ 之间；
• 用例保证数据格式都是正确的，不用考虑数据输入行数不够、注册信息不完整、字符串非法、优先级超限、时间格式不正确的问题；

样例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

说明

$App1$被注销后，$09:50$时刻没有应用注册，因此输出$NA$