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

杨世超 · 杨世超 · commit d49e41929daa · 2022-04-02T11:58:30.000+08:00
diff --git a/Solutions/1450. 在既定时间做作业的学生人数.md b/Solutions/1450. 在既定时间做作业的学生人数.md
@@ -0,0 +1,254 @@
+## [1450. 在既定时间做作业的学生人数](https://leetcode-cn.com/problems/number-of-students-doing-homework-at-a-given-time/)
+
+- 标签：数组
+- 难度：简单
+
+## 题目大意
+
+**描述**：给你两个长度相等的整数数组，一个表示开始时间的数组 `startTime` ，另一个表示结束时间的数组 `endTime`。再给定一个整数 `queryTime` 作为查询时间。已知第 `i` 名学生在 `startTime[i]` 时开始写作业并于 `endTime[i]` 时完成作业。
+
+**要求**：返回在查询时间 `queryTime` 时正在做作业的学生人数。即能够使 `queryTime` 处于区间 `[startTime[i], endTime[i]]` 的学生人数。
+
+**说明**：
+
+- $startTime.length == endTime.length$。
+- $1\le startTime.length \le 100$。
+- $1 \le startTime[i] \le endTime[i] \le 1000$。
+- $1 \le queryTime \le 1000$。
+
+**示例**：
+
+```Python
+输入	startTime = [4], endTime = [4], queryTime = 4
+输出	1
+解释	在查询时间只有一名学生在做作业。
+```
+
+## 解题思路
+
+### 思路 1：枚举算法
+
+- 维护一个用于统计在查询时间 `queryTime` 时正在做作业的学生人数的变量 `cnt`。然后遍历所有学生的开始时间和结束时间。
+- 如果 `queryTime` 在区间 `[startTime[i], endTime[i]]` 之间，即 `startTime[i] <= queryTime <= endTime[i]`，则令 `cnt` 加 `1`。
+- 遍历完输出统计人数 `cnt`。
+
+### 思路 1：枚举算法代码
+
+```Python
+class Solution:
+    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
+        cnt = 0
+        size = len(startTime)
+        for i in range(size):
+            if startTime[i] <= queryTime <= endTime[i]:
+                cnt += 1
+        return cnt
+```
+
+### 思路 2：线段树
+
+- 因为 $1 \le startTime[i] \le endTime[i] \le 1000$，所以我们可以维护一个区间为 `[0, 1000]` 的线段树，初始化所有区间值都为 `0`。
+- 然后遍历所有学生的开始时间和结束时间，并将区间 `[startTime[i], endTime[i]]` 值加 `1`。
+- 在线段树中查询 `queryTime` 对应的单点区间 `[queryTime, queryTime]` 的最大值为多少。
+
+### 思路 2：线段树代码
+
+```Python
+class TreeNode:
+    def __init__(self, val=0):
+        self.left = -1  # 区间左边界
+        self.right = -1  # 区间右边界
+        self.val = val  # 节点值（区间值）
+        self.lazy_tag = None  # 区间和问题的延迟更新标记
+
+
+# 线段树类
+class SegmentTree:
+    def __init__(self, nums, function):
+        self.size = len(nums)
+        self.tree = [TreeNode() for _ in range(4 * self.size)]  # 维护 TreeNode 数组
+        self.nums = nums  # 原始数据
+        self.function = function  # function 是一个函数，左右区间的聚合方法
+        if self.size > 0:
+            self.__build(0, 0, self.size - 1)
+
+    # 构建线段树，节点的存储下标为 index，节点的区间为 [left, right]
+    def __build(self, index, left, right):
+        self.tree[index].left = left
+        self.tree[index].right = right
+        if left == right:  # 叶子节点，节点值为对应位置的元素值
+            self.tree[index].val = self.nums[left]
+            return
+
+        mid = left + (right - left) // 2  # 左右节点划分点
+        left_index = index * 2 + 1  # 左子节点的存储下标
+        right_index = index * 2 + 2  # 右子节点的存储下标
+        self.__build(left_index, left, mid)  # 递归创建左子树
+        self.__build(right_index, mid + 1, right)  # 递归创建右子树
+        self.__pushup(index)  # 向上更新节点的区间值
+
+    # 向上更新下标为 index 的节点区间值，节点的区间值等于该节点左右子节点元素值的聚合计算结果
+    def __pushup(self, index):
+        left_index = index * 2 + 1  # 左子节点的存储下标
+        right_index = index * 2 + 2  # 右子节点的存储下标
+        self.tree[index].val = self.function(self.tree[left_index].val, self.tree[right_index].val)
+
+    # 单点更新，将 nums[i] 更改为 val
+    def update_point(self, i, val):
+        self.nums[i] = val
+        self.__update_point(i, val, 0, 0, self.size - 1)
+
+    # 单点更新，将 nums[i] 更改为 val。节点的存储下标为 index，节点的区间为 [left, right]
+    def __update_point(self, i, val, index, left, right):
+        if self.tree[index].left == self.tree[index].right:
+            self.tree[index].val = val  # 叶子节点，节点值修改为 val
+            return
+
+        mid = left + (right - left) // 2  # 左右节点划分点
+        left_index = index * 2 + 1  # 左子节点的存储下标
+        right_index = index * 2 + 2  # 右子节点的存储下标
+        if i <= mid:  # 在左子树中更新节点值
+            self.__update_point(i, val, left_index, left, mid)
+        else:  # 在右子树中更新节点值
+            self.__update_point(i, val, right_index, mid + 1, right)
+        self.__pushup(index)  # 向上更新节点的区间值
+
+    # 区间查询，查询区间为 [q_left, q_right] 的区间值
+    def query_interval(self, q_left, q_right):
+        return self.__query_interval(q_left, q_right, 0, 0, self.size - 1)
+
+    # 区间查询，在线段树的 [left, right] 区间范围中搜索区间为 [q_left, q_right] 的区间值
+    def __query_interval(self, q_left, q_right, index, left, right):
+        if left >= q_left and right <= q_right:  # 节点所在区间被 [q_left, q_right] 所覆盖
+            return self.tree[index].val  # 直接返回节点值
+        if right < q_left or left > q_right:  # 节点所在区间与 [q_left, q_right] 无关
+            return 0
+
+        self.__pushdown(index)
+
+        mid = left + (right - left) // 2  # 左右节点划分点
+        left_index = index * 2 + 1  # 左子节点的存储下标
+        right_index = index * 2 + 2  # 右子节点的存储下标
+        res_left = 0  # 左子树查询结果
+        res_right = 0  # 右子树查询结果
+        if q_left <= mid:  # 在左子树中查询
+            res_left = self.__query_interval(q_left, q_right, left_index, left, mid)
+        if q_right > mid:  # 在右子树中查询
+            res_right = self.__query_interval(q_left, q_right, right_index, mid + 1, right)
+        return self.function(res_left, res_right)  # 返回左右子树元素值的聚合计算结果
+
+    # 区间更新，将区间为 [q_left, q_right] 上的元素值修改为 val
+    def update_interval(self, q_left, q_right, val):
+        self.__update_interval(q_left, q_right, val, 0, 0, self.size - 1)
+
+    # 区间更新
+    def __update_interval(self, q_left, q_right, val, index, left, right):
+
+        if left >= q_left and right <= q_right:  # 节点所在区间被 [q_left, q_right] 所覆盖
+            if self.tree[index].lazy_tag:
+                self.tree[index].lazy_tag += val  # 将当前节点的延迟标记增加 val
+            else:
+                self.tree[index].lazy_tag = val  # 将当前节点的延迟标记增加 val
+            interval_size = (right - left + 1)  # 当前节点所在区间大小
+            self.tree[index].val += val * interval_size  # 当前节点所在区间每个元素值增加 val
+            return
+        if right < q_left or left > q_right:  # 节点所在区间与 [q_left, q_right] 无关
+            return 0
+
+        self.__pushdown(index)
+
+        mid = left + (right - left) // 2  # 左右节点划分点
+        left_index = index * 2 + 1  # 左子节点的存储下标
+        right_index = index * 2 + 2  # 右子节点的存储下标
+        if q_left <= mid:  # 在左子树中更新区间值
+            self.__update_interval(q_left, q_right, val, left_index, left, mid)
+        if q_right > mid:  # 在右子树中更新区间值
+            self.__update_interval(q_left, q_right, val, right_index, mid + 1, right)
+
+        self.__pushup(index)
+
+    # 向下更新下标为 index 的节点所在区间的左右子节点的值和懒惰标记
+    def __pushdown(self, index):
+        lazy_tag = self.tree[index].lazy_tag
+        if not lazy_tag:
+            return
+
+        left_index = index * 2 + 1  # 左子节点的存储下标
+        right_index = index * 2 + 2  # 右子节点的存储下标
+
+        if self.tree[left_index].lazy_tag:
+            self.tree[left_index].lazy_tag += lazy_tag  # 更新左子节点懒惰标记
+        else:
+            self.tree[left_index].lazy_tag = lazy_tag
+        left_size = (self.tree[left_index].right - self.tree[left_index].left + 1)
+        self.tree[left_index].val += lazy_tag * left_size  # 左子节点每个元素值增加 lazy_tag
+
+        if self.tree[right_index].lazy_tag:
+            self.tree[right_index].lazy_tag += lazy_tag  # 更新右子节点懒惰标记
+        else:
+            self.tree[right_index].lazy_tag = lazy_tag
+        right_size = (self.tree[right_index].right - self.tree[right_index].left + 1)
+        self.tree[right_index].val += lazy_tag * right_size  # 右子节点每个元素值增加 lazy_tag
+
+        self.tree[index].lazy_tag = None  # 更新当前节点的懒惰标记
+
+    # 获取 nums 数组
+    def get_nums(self):
+        for i in range(self.size):
+            self.nums[i] = self.query_interval(i, i)
+        return self.nums
+
+class Solution:
+    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
+        nums = [0 for _ in range(1010)]
+        self.ST = SegmentTree(nums, lambda x, y: max(x, y))
+        size = len(startTime)
+        for i in range(size):
+            self.ST.update_interval(startTime[i], endTime[i], 1)
+
+        return self.ST.query_interval(queryTime, queryTime)
+```
+
+### 思路 3：树状数组
+
+- 因为 $1 \le startTime[i] \le endTime[i] \le 1000$，所以我们可以维护一个区间为 `[0, 1000]` 的树状数组。
+- 注意：
+  - 树状数组中 `update(self, index, delta):` 指的是将对应元素 `nums[index] ` 加上 `delta`。
+  - `query(self, index):` 指的是 `index` 位置之前的元素和，即前缀和。
+- 然后遍历所有学生的开始时间和结束时间，将树状数组上 `startTime[i]` 的值增加 `1`，再将树状数组上`endTime[i]` 的值减少 `1`。
+- 则查询 `queryTime` 位置的前缀和即为答案。
+
+### 思路 3：树状数组代码
+
+```Python
+class BinaryIndexTree:
+
+    def __init__(self, n):
+        self.size = n
+        self.tree = [0 for _ in range(n + 1)]
+
+    def lowbit(self, index):
+        return index & (-index)
+
+    def update(self, index, delta):
+        while index <= self.size:
+            self.tree[index] += delta
+            index += self.lowbit(index)
+
+    def query(self, index):
+        res = 0
+        while index > 0:
+            res += self.tree[index]
+            index -= self.lowbit(index)
+        return res
+
+class Solution:
+    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
+        bit = BinaryIndexTree(1010)
+        size = len(startTime)
+        for i in range(size):
+            bit.update(startTime[i], 1)
+            bit.update(endTime[i] + 1, -1)
+        return bit.query(queryTime)
+```
+
