#1450

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Number of Students Doing Homework at a Given Time

Count the number of students doing homework at a given time using an array-driven solution approach.

Problem Statement

You are given two integer arrays startTime and endTime, along with an integer queryTime. Each student starts their homework at startTime[i] and ends it at endTime[i]. Your task is to determine how many students are doing homework at exactly queryTime.

For each student, if queryTime is between their startTime[i] and endTime[i], inclusive, they are doing homework at that time. Return the total count of students who are doing their homework at queryTime.

Examples

Example 1

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

Output: 1

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 also 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

The only student was doing their homework at the queryTime.

Constraints

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

Solution Approach

Brute Force Solution

Loop through each student's start and end times, checking if queryTime falls within their interval [startTime[i], endTime[i]]. This approach has a time complexity of O(n), where n is the length of the arrays.

Optimized Approach Using Prefix Sum

Use a prefix sum to track the number of students active at any time. This can reduce the time complexity for more advanced variations of the problem but may not provide a substantial improvement for this basic case.

Binary Search Approach

Although not optimal for this specific problem, using binary search can speed up solutions if extended to more complex constraints where time intervals are sorted or have other patterns.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The brute force solution has a time complexity of O(n), where n is the number of students, since each student's interval needs to be checked. The space complexity is O(1) for this approach, as we only need a constant amount of space to store the count of active students.

What Interviewers Usually Probe

The problem tests the candidate's ability to iterate over arrays and check conditions efficiently.
A good candidate will demonstrate knowledge of array-driven solutions and optimization techniques.
Look for efficient handling of edge cases such as a single student's homework or multiple overlapping intervals.

Common Pitfalls or Variants

Common pitfalls

Forgetting to include the endpoints of the interval, which may cause missing valid students.
Overcomplicating the solution by using unnecessary optimizations, when the problem can be solved with simple iteration.
Not handling edge cases like overlapping intervals or when startTime[i] equals endTime[i].

Follow-up variants

What if startTime and endTime were sorted? This would allow for more advanced solutions like binary search.
What if the number of students was significantly larger, requiring space or time optimizations?
Consider the situation where we need to return a range of times when students are doing homework, not just a single query time.

FAQ

What is the main pattern used to solve the 'Number of Students Doing Homework at a Given Time' problem?

The main pattern involves iterating through the start and end times of the students and checking if the queryTime falls within each student's homework period.

What are the time and space complexities for the brute force solution?

The time complexity is O(n) where n is the number of students, and the space complexity is O(1).

How can the solution be optimized if the number of students is large?

For large numbers of students, optimization might involve using a prefix sum or binary search, especially if the time intervals are sorted.

What edge cases should I consider for this problem?

Edge cases include handling single students, ensuring inclusive intervals, and managing cases where startTime[i] equals endTime[i].

Can the 'Number of Students Doing Homework at a Given Time' problem be generalized to a range of times?

Yes, the problem can be generalized by extending it to check if students are doing homework during any of the times in a range, instead of a single queryTime.

terminal

Solution

Solution 1: Direct Traversal

We can directly traverse the two arrays. For each student, we check if $\textit{queryTime}$ is within their homework time interval. If it is, we increment the answer by one.

1

2

3

4

5

class Solution:
    def busyStudent(
        self, startTime: List[int], endTime: List[int], queryTime: int
    ) -> int:
        return sum(x <= queryTime <= y for x, y in zip(startTime, endTime))

Continue Practicing

#1449 form largest integer with digits that add up to target #1452 people whose list of favorite companies is not a subset of another list #1453 maximum number of darts inside of a circular dartboard