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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

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

方法一：枚举

题目要求找到 queryTime 时正在做作业的学生人数，第 i 名学生的起始时间 startTime}[i] 和完成时间 endTime}[i] 如果满足 startTime}[i] \le \textit{queryTime} \le \textit{endTime}[i]，则可知该名学生在 queryTime 时一定正在作业。我们遍历所有学生的起始时间和结束时间，统计符合上述条件的学生总数即可。

[sol1-Python3]
1
2
3
class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        return sum(s <= queryTime <= e for s, e in zip(startTime, endTime))
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        int n = startTime.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (startTime[i] <= queryTime && endTime[i] >= queryTime) {
                ans++;
            }
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int n = startTime.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (startTime[i] <= queryTime && endTime[i] >= queryTime) {
                ans++;
            }
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int BusyStudent(int[] startTime, int[] endTime, int queryTime) {
        int n = startTime.Length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (startTime[i] <= queryTime && endTime[i] >= queryTime) {
                ans++;
            }
        }
        return ans;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
int busyStudent(int* startTime, int startTimeSize, int* endTime, int endTimeSize, int queryTime){
    int ans = 0;
    for (int i = 0; i < startTimeSize; i++) {
        if (startTime[i] <= queryTime && endTime[i] >= queryTime) {
            ans++;
        }
    }
    return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
var busyStudent = function(startTime, endTime, queryTime) {
    const n = startTime.length;
    let ans = 0;
    for (let i = 0; i < n; i++) {
        if (startTime[i] <= queryTime && endTime[i] >= queryTime) {
            ans++;
        }
    }
    return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
func busyStudent(startTime []int, endTime []int, queryTime int) (ans int) {
    for i, s := range startTime {
        if s <= queryTime && queryTime <= endTime[i] {
            ans++
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 数组的长度。只需遍历一遍数组即可。

  • 空间复杂度：O(1)。

方法二：差分数组

利用差分数组的思想，对差分数组求前缀和，可以得到统计出 t 时刻正在做作业的人数。我们初始化差分数组 cnt 每个元素都为 0，在每个学生的起始时间处 cnt}[\textit{startTime}[i]] 加 1，在每个学生的结束时间处 cnt}[\textit{endTime}[i] + 1] 减 1，因此我们可以统计出 queryTime 时刻正在做作业的人数为 \sum_{j=0}^{\textit{queryTime} }\textit{cnt}[j]。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        maxEndTime = max(endTime)
        if queryTime > maxEndTime:
            return 0
        cnt = [0] * (maxEndTime + 2)
        for s, e in zip(startTime, endTime):
            cnt[s] += 1
            cnt[e + 1] -= 1
        return sum(cnt[:queryTime + 1])
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        int n = startTime.size();
        int maxEndTime = *max_element(endTime.begin(), endTime.end());
        if (queryTime > maxEndTime) {
            return 0;
        }
        vector<int> cnt(maxEndTime + 2);
        for (int i = 0; i < n; i++) {
            cnt[startTime[i]]++;
            cnt[endTime[i] + 1]--;
        }
        int ans = 0;
        for (int i = 0; i <= queryTime; i++) {
            ans += cnt[i];
        }
        return ans;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int n = startTime.length;
        int maxEndTime = Arrays.stream(endTime).max().getAsInt();
        if (queryTime > maxEndTime) {
            return 0;
        }
        int[] cnt = new int[maxEndTime + 2];
        for (int i = 0; i < n; i++) {
            cnt[startTime[i]]++;
            cnt[endTime[i] + 1]--;
        }
        int ans = 0;
        for (int i = 0; i <= queryTime; i++) {
            ans += cnt[i];
        }
        return ans;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int BusyStudent(int[] startTime, int[] endTime, int queryTime) {
        int n = startTime.Length;
        int maxEndTime = endTime.Max();
        if (queryTime > maxEndTime) {
            return 0;
        }
        int[] cnt = new int[maxEndTime + 2];
        for (int i = 0; i < n; i++) {
            cnt[startTime[i]]++;
            cnt[endTime[i] + 1]--;
        }
        int ans = 0;
        for (int i = 0; i <= queryTime; i++) {
            ans += cnt[i];
        }
        return ans;
    }
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define MAX(a, b) ((a) > (b) ? (a) : (b))

int busyStudent(int* startTime, int startTimeSize, int* endTime, int endTimeSize, int queryTime){
    int maxEndTime = 0;
    for (int i = 0; i < endTimeSize; i++) {
        maxEndTime = MAX(maxEndTime, endTime[i]);
    }
    if (queryTime > maxEndTime) {
        return 0;
    }
    int *cnt = (int *)malloc(sizeof(int) * (maxEndTime + 2));
    memset(cnt, 0, sizeof(maxEndTime) * (maxEndTime + 2));
    for (int i = 0; i < startTimeSize; i++) {
        cnt[startTime[i]]++;
        cnt[endTime[i] + 1]--;
    }
    int ans = 0;
    for (int i = 0; i <= queryTime; i++) {
        ans += cnt[i];
    }
    free(cnt);
    return ans;
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var busyStudent = function(startTime, endTime, queryTime) {
    const n = startTime.length;
    const maxEndTime = _.max(endTime);
    if (queryTime > maxEndTime) {
        return 0;
    }
    const cnt = new Array(maxEndTime + 2).fill(0);
    for (let i = 0; i < n; i++) {
        cnt[startTime[i]]++;
        cnt[endTime[i] + 1]--;
    }
    let ans = 0;
    for (let i = 0; i <= queryTime; i++) {
        ans += cnt[i];
    }
    return ans;
};
[sol2-Golang]
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
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 + \textit{queryTime})，其中 n 为数组的长度，queryTime 为给定的查找时间。首先需要遍历一遍数组，需要的时间为 O(n)，然后需要查分求和求出 queryTime 时间点正在作业的学生总数，需要的时间为 O(\textit{queryTime})，因此总的时间为 O(n + \textit{queryTime})。

  • 空间复杂度：O(\max(\textit{endTime}))。

方法三：二分查找

对于每个学生的作业时间 [\textit{startTime}[i], \textit{endTime}[i]]，一定满足 startTime}[i]\le \textit{endTime}[i]。如果第 i 名学生在 queryTime 时正在作业，则一定满足 startTime}[i] \le \textit{queryTime} \le \textit{endTime}[i]。设起始时间小于等于 queryTime 的学生集合为 lessStart，设结束时间小于 queryTime 的学生集合为 lessEnd，则根据上述推理可以知道 lessEnd} \in \textit{lessStart，我们从 lessStart 去除 lessEnd 的子集部分即为符合条件的学生集合。因此我们通过二分查找找到始时间小于等于 queryTime 的学生人数，然后减去结束时间小于 queryTime 的学生人数，最终结果即为符合条件要求。

[sol3-Python3]
1
2
3
4
5
class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        startTime.sort()
        endTime.sort()
        return bisect_right(startTime, queryTime) - bisect_left(endTime, queryTime)
[sol3-C++]
1
2
3
4
5
6
7
8
9
10
class Solution {
public: 
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        sort(startTime.begin(), startTime.end());
        sort(endTime.begin(), endTime.end());
        int lessStart = upper_bound(startTime.begin(), startTime.end(), queryTime) - startTime.begin();
        int lessEnd = lower_bound(endTime.begin(), endTime.end(), queryTime) - endTime.begin();
        return lessStart - lessEnd;
    }
};
[sol3-Java]
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
class Solution {
    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        Arrays.sort(startTime);
        Arrays.sort(endTime);
        int lessStart = upperbound(startTime, 0, startTime.length - 1, queryTime);
        int lessEnd = lowerbound(endTime, 0, endTime.length - 1, queryTime);
        return lessStart - lessEnd;
    }

    public static int upperbound(int[] arr, int l, int r, int target) {
        int ans = r + 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] > target) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }

    public static int lowerbound(int[] arr, int l, int r, int target) {
        int ans = r + 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] >= target) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
}
[sol3-C#]
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
public class Solution {
    public int BusyStudent(int[] startTime, int[] endTime, int queryTime) {
        Array.Sort(startTime);
        Array.Sort(endTime);
        int lessStart = Upperbound(startTime, 0, startTime.Length - 1, queryTime);
        int lessEnd = Lowerbound(endTime, 0, endTime.Length - 1, queryTime);
        return lessStart - lessEnd;
    }

    public static int Upperbound(int[] arr, int l, int r, int target) {
        int ans = r + 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] > target) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }

    public static int Lowerbound(int[] arr, int l, int r, int target) {
        int ans = r + 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (arr[mid] >= target) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
}
[sol3-C]
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
static inline int cmp(const void *pa, const void *pb) {
    return *(int *)pa - *(int *)pb;
}

static int upperbound(const int *arr, int l, int r, int target) {
    int ans = r + 1;
    while (l <= r) {
        int mid = l + ((r - l) >> 1);
        if (arr[mid] > target) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

static int lowerbound(const int *arr, int l, int r, int target) {
    int ans = r + 1;
    while (l <= r) {
        int mid = l + ((r - l) >> 1);
        if (arr[mid] >= target) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

int busyStudent(int* startTime, int startTimeSize, int* endTime, int endTimeSize, int queryTime){
    qsort(startTime, startTimeSize, sizeof(int), cmp);
    qsort(endTime, endTimeSize, sizeof(int), cmp);
    int lessStart = upperbound(startTime, 0, startTimeSize - 1, queryTime);
    int lessEnd = lowerbound(endTime, 0, endTimeSize - 1, queryTime);
    return lessStart - lessEnd;
}
[sol3-JavaScript]
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
var busyStudent = function(startTime, endTime, queryTime) {
    startTime.sort((a, b) => a - b);
    endTime.sort((a, b) => a - b);
    const lessStart = upperbound(startTime, 0, startTime.length - 1, queryTime);
    const lessEnd = lowerbound(endTime, 0, endTime.length - 1, queryTime);
    return lessStart - lessEnd;
}

const upperbound = (arr, l, r, target) => {
    let ans = r + 1;
    while (l <= r) {
        const mid = l + ((r - l) >> 1);
        if (arr[mid] > target) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

const lowerbound = (arr, l, r, target) => {
    let ans = r + 1;
    while (l <= r) {
        let mid = l + ((r - l) >> 1);
        if (arr[mid] >= target) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
};
[sol3-Golang]
1
2
3
4
5
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(n \log n)，其中 n 为 数组的长度。排序需要的时间为 O(n \log n)，二分查找的时间复杂度为 O(\log n)。

  • 空间复杂度：O(\log n)。排序需要的栈空间为 O(\log n)。

 Comments
On this page
1450-在既定时间做作业的学生人数