在既定时间做作业的学生人数Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你两个整数数组 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

# 思路

动态点开线段树

# 解法


class Solution {
     class Node {
            Node left, right;
            int val, add;
        }
        private int N = (int) 1e9;
        private Node root = new Node();
        public void update(Node node, int start, int end, int l, int r, int val) {
            if (l <= start && end <= r) {
                node.val +=val;
                node.add +=val;
                return;
            }
            pushDown(node);
            int mid = (start + end) >> 1;
            if (l <= mid) update(node.left, start, mid, l, r, val);
            if (r > mid) update(node.right, mid + 1, end, l, r, val);
            pushUp(node);
        }
        public int query(Node node, int start, int end, int l, int r) {
            if (l <= start && end <= r) return node.val;
            pushDown(node);
            int mid = (start + end) >> 1, ans = 0;
            if (l <= mid) ans =Math.max(ans,query(node.left, start, mid, l, r));
            if (r > mid) ans = Math.max(ans,query(node.right, mid + 1, end, l, r));
            return ans;
        }
        private void pushUp(Node node) {
            node.val = Math.max(node.left.val,node.right.val);
        }
        private void pushDown(Node node) {
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            if (node.add == 0) return;
            node.left.val += node.add;
            node.right.val += node.add;
            node.left.add += node.add;
            node.right.add += node.add;
            node.add = 0;
        }
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
           for (int i=0;i<startTime.length;i++)
           {
               int s=startTime[i];
               int e=endTime[i];
               update(root,1,N,s,e,1);
           }
           return query(root,1,N,queryTime,queryTime);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

# 总结

分析出几种情况，然后分别对各个情况实现

#Java