LeetCode 1450 - Number of Students Doing Homework at a Given Time

LeetCode Problem 1450

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

This problem asks us to determine how many students are doing homework at a specific point in time, given arrays representing when each student starts and finishes their homework. More concretely, we have two arrays startTime and endTime of the same length. Each index i represents one student: startTime[i] is when they begin, and endTime[i] is when they finish. We are also given a single integer queryTime and need to count how many students are active at that exact time. The time intervals are inclusive, meaning a student is considered active at both startTime[i] and endTime[i].

The constraints are straightforward: the arrays have lengths between 1 and 100, and the values are all positive integers not exceeding 1000. These constraints indicate that a simple linear solution is acceptable, as even a brute-force check over all students is efficient. Edge cases to watch out for include students who start and finish at the same time, queryTime being before all start times, after all end times, or exactly matching the start or end of an interval.

Approaches

The most direct approach is brute force: iterate over each student and check if queryTime falls within their interval [startTime[i], endTime[i]]. If it does, increment a counter. This method is simple and works within the problem constraints.

The key observation for an optimal approach is that no complex data structure or sorting is necessary. Since the arrays are small, iterating over each element and checking a condition is efficient. Any attempt to use more advanced techniques, like prefix sums or interval trees, would be overkill for this problem.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Iterate through each student and count if queryTime is within [startTime[i], endTime[i]]
Optimal	O(n)	O(1)	Same as brute force; small input size makes linear iteration sufficient

Algorithm Walkthrough

1. Initialize a counter variable count to zero. This will store the number of students active at queryTime.
2. Iterate over all students using their indices.
3. For each student i, check if queryTime is greater than or equal to startTime[i] and less than or equal to endTime[i].
4. If the condition is true, increment count by one.
5. After processing all students, return the value of count.

Why it works: Each student's interval is explicitly checked against queryTime. Since the intervals are inclusive, any student whose start and end times include queryTime is counted exactly once. No student is double-counted, and all relevant students are included, guaranteeing correctness.

Python Solution

from typing import List

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

This Python implementation follows the algorithm exactly. We initialize a counter, iterate through the indices of startTime and endTime, check the inclusive condition for queryTime, and increment the counter when the condition is satisfied. Finally, we return the total count.

Go Solution

func busyStudent(startTime []int, endTime []int, queryTime int) int {
    count := 0
    for i := 0; i < len(startTime); i++ {
        if startTime[i] <= queryTime && queryTime <= endTime[i] {
            count++
        }
    }
    return count
}

The Go version mirrors the Python solution. A counter is initialized, a simple for loop iterates over the slice indices, and an inclusive comparison checks each student's interval. Go handles slices safely, so no nil checks are required given the problem constraints.

Worked Examples

Example 1:

startTime = [1,2,3]
endTime = [3,2,7]
queryTime = 4

Step by step:

i	startTime[i]	endTime[i]	queryTime in interval?	count
0	1	3	No	0
1	2	2	No	0
2	3	7	Yes	1

Output: 1

Example 2:

startTime = [4]
endTime = [4]
queryTime = 4

Step by step:

i	startTime[i]	endTime[i]	queryTime in interval?	count
0	4	4	Yes	1

Output: 1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate once through all students, performing a constant-time comparison for each.
Space	O(1)	Only a counter variable is used; no additional memory scales with input size.

The complexity is optimal for this problem because each student must be checked individually.

Test Cases

# Provided examples
assert Solution().busyStudent([1,2,3], [3,2,7], 4) == 1  # single active student
assert Solution().busyStudent([4], [4], 4) == 1           # only one student, exact match

# Edge cases
assert Solution().busyStudent([1,2,3], [1,2,3], 4) == 0   # queryTime after all intervals
assert Solution().busyStudent([1,2,3], [3,4,5], 1) == 1   # queryTime at start of interval
assert Solution().busyStudent([1,2,3], [3,4,5], 5) == 1   # queryTime at end of interval
assert Solution().busyStudent([1]*100, [100]*100, 50) == 100 # maximum length, all active

Test	Why
[1,2,3], [3,2,7], 4	Basic scenario with only one active student
[4], [4], 4	Single student edge case, exact query match
[1,2,3], [1,2,3], 4	Query time after all intervals, expect 0
[1,2,3], [3,4,5], 1	Query time at the start of first interval
[1,2,3], [3,4,5], 5	Query time at the end of last interval
[1]*100, [100]*100, 50	Stress test, all students active at queryTime

Edge Cases

One important edge case is when queryTime is before all start times. This could happen if all students start after the query, and the algorithm must correctly return zero. Another edge case is when queryTime equals the start or end of an interval. Since intervals are inclusive, these students should be counted. Finally, the edge case of all students being active at the same time tests that the algorithm can handle maximum array lengths and correctly count multiple students simultaneously without errors. The implementation handles all these situations through direct comparison using <= and >=.