LC 1450. 在既定时间做作业的学生人数

题目描述

这是 LeetCode 上的 1450. 在既定时间做作业的学生人数 ，难度为 简单。

给你两个整数数组 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.length$
• $1 <= startTime.length <= 100$
• $1 <= startTime[i] <= endTime[i] <= 1000$
• $1 <= queryTime <= 1000$

---

差分

为了方便，我们令 startTime 为 st，令 endTime 为 et，令 queryTime 为 t。

问题涉及「区间修改」+「单点查询」，是一道关于「差分」的模板题。

对差分不熟悉的同学，可以查看前置 🧀 : 差分入门

利用时间点数据范围为 $1e3$，我们建立一个 $1e3$ 大小的差分数组 c，对于时间段 $[st[i], et[i]]$ 而言，我们只需在差分数组 $c[st[i]]$ 上进行自增，在 $c[et[i] + 1]$ 进行自减，即可实现 $O(1)$ 复杂度对范围 $[st[i], et[i]]$ 的标记。

当处理完后，只需要对 c 执行「前缀和」操作，即可查询每个时间点被标记的次数（由于我们只需要求时间点 t 的覆盖次数，因此我们只需求 $[0, t]$ 范围的前缀和即可）。

Java 代码：

class Solution {
    public int busyStudent(int[] st, int[] et, int t) {
        int[] c = new int[1010];
        for (int i = 0; i < st.length; i++) {
            c[st[i]]++; c[et[i] + 1]--;
        }
        for (int i = 1; i <= t; i++) c[i] += c[i - 1];
        return c[t];
    }
}

C++ 代码：

class Solution {
public:
    int busyStudent(vector<int>& st, vector<int>& et, int t) {
        vector<int> c(1010, 0);
        for (int i = 0; i < st.size(); i++) {
            c[st[i]] += 1; c[et[i] + 1] -= 1;
        }
        for (int i = 1; i <= t; ++i) c[i] += c[i - 1];
        return c[t];
    }
};

Python 代码：

class Solution:
    def busyStudent(self, st: List[int], et: List[int], t: int) -> int:
        c = [0] * 1010
        for i in range(len(st)):
            c[st[i]] += 1
            c[et[i] + 1] -= 1
        for i in range(t + 1):
            c[i] += c[i - 1]
        return c[t]

TypeScript 代码：

function busyStudent(st: number[], et: number[], t: number): number {
    const c = new Array<number>(1010).fill(0)
    for (let i = 0; i < st.length; i++) {
        c[st[i]]++; c[et[i] + 1]--;
    }
    for (let i = 1; i <= t; i++) c[i] += c[i - 1];
    return c[t]
};

• 时间复杂度：创建差分数组复杂度为 $O(C)$，其中 $C = 1e3$ 为值域大小，随后使用差分数组进行区间标记，复杂度为 $O(n)$，构建前缀和数组用于查询复杂度为 $O(t)$，整体复杂度为 $O(C)$
• 空间复杂度：$O(C)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1450 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。