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

题目描述

智能手机方便了我们生活的同时，也侵占了我们不少的时间。“手机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表示空闲时间

用例

题目解析

本题数量级较小，可以考虑暴力破解。

本题每注册一个App_registering前，都要去和已注册的所有App_registered进行比较：

• 注册时段是否有冲突？

1. 如果没有冲突，则继续和下一个App_registered比较
2. 如果有冲突，则比较优先级2.1. App_registering 的优先级高于（>）App_registered，则App_registered需要被注销，此时不能直接进行注销动作，因为我们需要确保 App_registering 可以注册后，才能进行注销。2.2. App_registering 的优先级不高于（≤）App_registered，则App_registering不能注册，即终止后续比较

本题比较两个App注册时段冲突的方式，可以将App的注册时段的时间点信息，转化为分钟数数值，比如：

10:29

可以转化为：

10 * 60 + 29 = 629

这样两个App的时段比较，其实判断两个区间是否有交集，假设两个时段分别为

[s1, e1] 和 [s2, e2]

只要满足

s1 >= e2 或者 s2 >= e1 即可说明两个区间无交集，注意根据题目说明

注册信息中的时间段包含起始时间点，不包含结束时间点

上面两个区间均为左闭右开区间。

且区间保证左边界>右边界，因为题目说明

起始时间需小于结束时间，否则注册不上

即，一个App是否可以注册需要先判断其左边界是否大于右边界

import Foundation

struct App {
    var name = ""
    var priority = 0
    var startTime = 0
    var endTime = 0

    init(name: String = "", priority: Int = 0, startTime: String = "00:00", endTime: String = "00:00") {
        self.name = name
        self.priority = priority
        self.startTime = timeToInt(startTime)
        self.endTime = timeToInt(endTime)
    }

    func timeToInt(_ startTime: String = "00:00") -> Int {
        let times = startTime.split(separator: ":").map { Int($0) ?? 0 }
        return (times.first ?? 0) * 60 + (times.last ?? 0)
    }
}

func ODTest_31() {
    print("第一行表示注册的App数量 N（N ≤ 100）")
    let N = Int(readLine() ?? "") ?? 0
    print("第二部分包括 N 行，每行表示一条App注册数据")
    var Apps: [App] = []
    for _ in 0 ..< N {
        let data = (readLine() ?? "").split(separator: " ").map { String($0) }
        let app = App(name: data[0], priority: Int(data[1]) ?? 0, startTime: data[2], endTime: data[3])
        Apps.append(app)
    }
    var registereds: [App] = []
    for i in 0 ..< N {
        let app = Apps[i]
        if app.startTime >= app.endTime {
            continue
        }
        // 如果App的优先级相同，则后添加的App不能注册
        guard let _ = registereds.firstIndex(where: {
            $0.priority == app.priority
        }) else {
            continue
        }

        // 如果高优先级的App时间和低优先级的时段有冲突，则系统会自动注销低优先级的时段
        if let item = registereds.first(where: {
            $0.startTime >= app.endTime || app.startTime >= $0.endTime
        }) {
            if item.priority < app.priority {
                registereds.removeAll(where: { $0.name == item.name && $0.endTime == item.endTime && $0.startTime == item.startTime })
                registereds.append(app)
            }
        } else {
            registereds.append(app)
        }
    }

    // 需要查询的时间点
    print("需要查询的时间点")
    let data = (readLine() ?? "")
    let time = App().timeToInt(data)
    guard let item = registereds.first(where: {
        $0.startTime <= time || $0.endTime >= time
    }) else {
        print("无")
        return
    }
    print("\(item.name)")
}