Number of Students Doing Homework at a Given Time

Difficulty: Easy | Acceptance: 75.90% | Paid: No Topics: Array

Given two integer arrays startTime and endTime and an integer queryTime. The ith student started doing their homework at the time startTime[i] and finished it at time endTime[i].

Return the number of students doing their homework at time queryTime. More formally, return the number of students where queryTime lays in the interval [startTime[i], endTime[i]] inclusive.

• Examples
• Constraints
• Linear Scan
• Prefix Sum (Difference Array)

Examples

Example 1:

Input: startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
Output: 1
Explanation: We have 3 students where:
The first student started doing homework at time 1 and finished at time 3 and wasn't doing anything at time 4.
The second student started doing homework at time 2 and finished at time 2 and wasn't doing anything at time 4.
The third student started doing homework at time 3 and finished at time 7 and was the only student doing homework at time 4.

Example 2:

Input: startTime = [4], endTime = [4], queryTime = 4
Output: 1

Constraints

startTime.length == endTime.length
1 <= startTime.length <= 100
1 <= startTime[i] <= endTime[i] <= 1000
1 <= queryTime <= 1000

Linear Scan

Intuition The most straightforward way to solve this problem is to iterate through each student’s time interval and check if the queryTime falls within that range.

Steps

• Initialize a counter variable to 0.
• Iterate through the arrays startTime and endTime simultaneously.
• For each student, check if startTime[i] <= queryTime and queryTime <= endTime[i].
• If the condition is true, increment the counter.
• Return the counter after the loop finishes.

from typing import List

class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        count = 0
        for s, e in zip(startTime, endTime):
            if s <= queryTime <= e:
                count += 1
        return count

Complexity

• Time: O(n), where n is the number of students. We iterate through the list once.
• Space: O(1), we only use a constant amount of extra space for the counter.
• Notes: This is the most optimal solution for general cases where time constraints are not bounded to a small range.

Prefix Sum (Difference Array)

Intuition Since the constraints specify that startTime[i] and endTime[i] are bounded by 1000, we can use a difference array (or prefix sum technique) to mark the start and end of each student’s homework interval. This allows us to calculate the number of active students at any given time in O(1) lookup after O(n) preprocessing.

Steps

• Initialize an array diff of size 1002 (to accommodate endTime + 1) with zeros.
• Iterate through the students. For each student, increment diff[startTime[i]] by 1 and decrement diff[endTime[i] + 1] by 1.
• Compute the prefix sum of the diff array. The value at index i in the resulting array represents the number of students doing homework at time i.
• Return the value at diff[queryTime].

from typing import List

class Solution:
    def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
        # Constraints say max time is 1000, so we need size 1002 for end+1
        diff = [0] * 1002
        
        for s, e in zip(startTime, endTime):
            diff[s] += 1
            diff[e + 1] -= 1
            
        # Calculate prefix sum up to queryTime
        count = 0
        for i in range(queryTime + 1):
            count += diff[i]
            
        return count

Complexity

• Time: O(n + T), where n is the number of students and T is the maximum time value (1000). Since T is constant, this is effectively O(n).
• Space: O(T), to store the difference array.
• Notes: This approach is efficient if there are multiple queries for different times, as the prefix sum array can be built once and queried in O(1). For a single query, the Linear Scan approach is simpler and uses less memory.