【2022-08-19每日一题】1450. 在既定时间做作业的学生人数
2022-08-19
2分钟阅读时长
2022-08-19每日一题：1450. 在既定时间做作业的学生人数
- 难度：Easy
- 标签：数组
给你两个整数数组 startTime（开始时间）和 endTime（结束时间），并指定一个整数 queryTime 作为查询时间。
已知，第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。
请返回在查询时间 queryTime 时正在做作业的学生人数。形式上，返回能够使 queryTime 处于区间 [startTime[i], endTime[i]]（含）的学生人数。
示例 1：
输入：startTime = [1,2,3], endTime = [3,2,7], queryTime = 4 输出：1 解释：一共有 3 名学生。 第一名学生在时间 1 开始写作业，并于时间 3 完成作业，在时间 4 没有处于做作业的状态。 第二名学生在时间 2 开始写作业，并于时间 2 完成作业，在时间 4 没有处于做作业的状态。 第三名学生在时间 3 开始写作业，预计于时间 7 完成作业，这是是唯一一名在时间 4 时正在做作业的学生。
示例 2：
输入：startTime = [4], endTime = [4], queryTime = 4 输出：1 解释：在查询时间只有一名学生在做作业。
示例 3：
输入：startTime = [4], endTime = [4], queryTime = 5 输出：0
示例 4：
输入：startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7 输出：0
示例 5：
输入：startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5 输出：5
提示：
startTime.length == endTime.length1 <= startTime.length <= 1001 <= startTime[i] <= endTime[i] <= 10001 <= queryTime <= 1000
最容易想到的解法
func busyStudent(startTime []int, endTime []int, queryTime int) (ans int) {
for i, start := range startTime {
if start <= queryTime && queryTime <= endTime[i] {
ans++
}
}
return ans
}
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)
方法二：差分数组（多此一举的解法）
我们建立一个差分数组 cnt，对于时间段 [startTime[i],endTime[i]] 而言，我们只需在差分数组 cnt[startTime[i]] 上进行自增，在cnt[endTime[i]+1] 进行自减，即可实现 O(1) 复杂度对范围 [startTime[i],endTime[i]] 的标记。
当处理完后，只需要对 cnt 执行「前缀和」操作，即可查询每个时间点被标记的次数（由于我们只需要求时间点 t 的覆盖次数，因此我们只需求 [0,t] 范围的前缀和即可）。
func busyStudent(startTime []int, endTime []int, queryTime int) (ans int) {
// 求最大结束时间
maxEndTime := 0
for _, e := range endTime {
maxEndTime = max(maxEndTime, e)
}
if queryTime > maxEndTime {
return
}
cnt := make([]int, maxEndTime+2)
for i, s := range startTime {
cnt[s]++
cnt[endTime[i]+1]--
}
for _, c := range cnt[:queryTime+1] {
ans += c
}
return
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
复杂度分析
- 时间复杂度：O(n+queryTime)
- 空间复杂度：O(max(endTime))
方法三：二分查找（多此一举的解法）
func busyStudent(startTime []int, endTime []int, queryTime int) (ans int) {
sort.Ints(startTime)
sort.Ints(endTime)
return sort.SearchInts(startTime, queryTime+1) - sort.SearchInts(endTime, queryTime)
}
复杂度分析
- 时间复杂度：O(nlogn)
- 空间复杂度：O(logn)