Given two integer arrays startTime and endTime and given 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.
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 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 Explanation: The only student was doing their homework at the queryTime.
Constraints:
startTime.length == endTime.length1 <= startTime.length <= 1001 <= startTime[i] <= endTime[i] <= 10001 <= queryTime <= 1000Problem Overview: You get two arrays: startTime and endTime. Each pair represents when a student starts and finishes homework. Given a queryTime, count how many students are still working at that moment (where startTime[i] ≤ queryTime ≤ endTime[i]).
Approach 1: Brute Force Interval Check (O(n) time, O(1) space)
Iterate through every student and check whether the query time falls inside that student's homework interval. For each index i, verify the condition startTime[i] ≤ queryTime ≤ endTime[i]. If the condition holds, increment the counter. This direct scan works because the intervals are independent and you only need a simple comparison per student. The algorithm performs a single pass over the array, so the time complexity is O(n) with constant extra memory.
Approach 2: Binary Search on Sorted Times (O(n log n) preprocessing, O(log n) query)
If you need to answer multiple queries, sorting becomes useful. Store all start times and end times separately and sort them. Use binary search to count how many students started homework at or before queryTime, and how many finished before queryTime. The difference between these two counts gives the number of active students. Each query runs in O(log n) time after sorting, with O(n) extra storage for the sorted arrays. This technique treats intervals as events and leverages efficient search instead of scanning every element.
Recommended for interviews: The brute force scan is usually the expected solution because the constraints are small and the logic is clean. Interviewers want to see that you correctly interpret the inclusive interval condition. The binary search variation demonstrates deeper understanding of interval counting and sorting, especially when the problem extends to multiple queries.
The brute force approach is straightforward. For every student, check if their homework period, defined by startTime[i] and endTime[i], includes the queryTime. This involves iterating through each student's start and end times and counting the number of students for whom the condition holds true.
This C solution iterates through the lists startTime and endTime synchronously, checks the condition for each student, and maintains a count of students who are doing homework at queryTime.
Time Complexity: O(n) where n is the number of students.
Space Complexity: O(1) as we are using a constant amount of extra space.
For this approach, we assume that the intervals in startTime and endTime are sorted, which allows us to use binary search. However, since this optimization is only valid on sorted data, it's generally not applicable unless additional constraints are applied.
Given the constraints and limitations of the standard C libraries, sticking to the brute force approach is recommended for correctness unless you manually implement sorting and searching routines.
Time Complexity: Approach generally could be O(log n) for sorted arrays, but implemented as O(n) due to constraints.
Space Complexity: O(1).
We can directly traverse the two arrays. For each student, we check if queryTime is within their homework time interval. If it is, we increment the answer by one.
After the traversal, we return the answer.
The time complexity is O(n), where n is the number of students. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n) where n is the number of students. |
| Binary Search Approach (Optimized for Sorted Times) | Time Complexity: Approach generally could be O(log n) for sorted arrays, but implemented as O(n) due to constraints. |
| Direct Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Interval Check | O(n) | O(1) | Best for a single query or small input sizes. Simple and interview-friendly. |
| Binary Search on Sorted Times | O(n log n) preprocessing, O(log n) query | O(n) | Useful when handling multiple query times or when the intervals are reused repeatedly. |
LeetCode#1450 Number of Students Doing Homework at a Given Time - Python • CodeJulian • 497 views views
Watch 9 more video solutions →Practice Number of Students Doing Homework at a Given Time with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor