华为OD统一考试 - 手机App防沉迷系统
题目描述
智能手机方便了我们生活的同时,也侵占了我们不少的时间。“手机App防沉迷系统”能够让我们每天合理地规划手机App使用时间,在正确的时间做正确的事。
它的大概原理是这样的:
- 在一天24小时内,可以注册每个App的允许使用时段
- 一个时间段只能使用一个App
- 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
数据说明如下:
- N行注册数据以空格分隔,四项数依次表示:App名称、优先级、起始时间、结束时间
- 优先级1~5,数字越大,优先级越高
- 时间格式 HH:MM,小时和分钟都是两位,不足两位前面补0
- 起始时间需小于结束时间,否则注册不上
- 注册信息中的时间段包含起始时间点,不包含结束时间点
输出描述
输出一个字符串,表示App名称,或NA表示空闲时间
用例
输入 | 1 App1 1 09:00 10:00 09:30 |
输出 | App1 |
说明 | App1注册在9点到10点间,9点半可用的应用名是App1 |
输入 | 2 App1 1 09:00 10:00 App2 2 09:10 09:30 09:20 |
输出 | App2 |
说明 | App1和App2的时段有冲突,App2优先级高,注册App2之后,App1自动注销,因此输出App2。 |
输入 | 2 App1 1 09:00 10:00 App2 2 09:10 09:30 09:50 |
输出 | NA |
说明 | 无 |
题目解析
本题数量级较小,可以考虑暴力破解。
本题每注册一个App_registering前,都要去和已注册的所有App_registered进行比较:
- 注册时段是否有冲突?
- 如果没有冲突,则继续和下一个App_registered比较
- 如果有冲突,则比较优先级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)") }
本专栏给大家提供了华为2024最新华为OD 题目汇总。华为OD机试刷题记录机考算法题库,帮助你上岸华为。提供C++/Java、JavaScript、Python四种语言的解法。