1450. Number of Students Doing Homework at a Given Time
Problem Description
The problem presents a scenario where multiple students have a record of when they started (startTime
) and finished (endTime
) their homework. These times are captured in two integer arrays where each element corresponds to an individual student. There's also a specific time called queryTime
, which is the time we are interested in examining.
The task is to determine how many students were in the process of doing their homework at that exact queryTime
. In other words, for a student to be counted, the queryTime
must be between their startTime
(inclusive) and endTime
(inclusive). If the queryTime
is equal to a student's startTime
or endTime
, that student is also counted.
Therefore, our primary objective is to scan through each student's start and end times and count how many students are within the range that includes the queryTime
.
Intuition
The intuitive approach to solving this problem involves iterating through the set of students' start and end times, checking whether the queryTime
falls between the two times.
Given that we have pairs of start and end times, we can use the zip
function in Python that conveniently merges the two arrays together. This means we will get a combined iterable where each element is a tuple (a, b)
, where a
comes from startTime
and b
comes from endTime
.
We check for each pair (a, b)
whether queryTime
is greater than or equal to a
(startTime) and less than or equal to b
(endTime). The expression a <= queryTime <= b
will return True
if queryTime
is within the range; otherwise, it will return False
.
By iterating over all these pairs and summing up the number of True
results, we determine how many students were doing their homework at queryTime
. The Python built-in function sum
can be used to add up True
values (each treated as 1
) easily.
This approach does not necessitate explicit loops or conditionals; it can be executed as a one-liner within the busyStudent
method, making it both efficient and concise.
Solution Approach
The solution uses a simple but effective algorithm that involves the following steps and components:
-
Zipping the Arrays: The
zip
function takes two lists,startTime
andendTime
, and combines them into a single iterable. Each element of this iterable is a tuple consisting of corresponding elements from the two lists (i.e., the start and end time for a single student). -
List Comprehension and Conditional Expressions: A list comprehension is used to iterate through each tuple of start and end times. It applies a conditional expression
a <= queryTime <= b
for each tuple(a, b)
, wherea
andb
are the start and end times, respectively. This expression returnsTrue
ifqueryTime
is within the inclusive range[a, b]
; otherwise, it returnsFalse
. -
Summation of True Instances: Python treats
True
as1
andFalse
as0
. Thesum
function is used to add up all the results of the conditional expressions within the list comprehension. Effectively, this adds up all1
s (whenever the condition isTrue
), which corresponds to counting the number of students who are busy atqueryTime
. -
Return the Count: The result of the
sum
is the total number of students doing their homework at thequeryTime
, which is then returned by the function.
By leveraging Python's built-in functions and language features, this solution is concise and eliminates the need for explicit loops or if-else conditional statements. The list comprehension elegantly handles the iteration and conditional checks in a single line of code, making it an exemplary demonstration of Python’s capabilities for compact code that is still readable and efficient.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the following simple example to illustrate the solution approach:
Suppose we have three students with the following startTime
and endTime
to represent when each student started and finished their homework:
1startTimes = [1, 2, 3] 2endTimes = [3, 2, 7] 3queryTime = 2
We want to determine how many students were doing their homework at the queryTime
of 2
.
Step by Step Walkthrough:
-
Zipping the Arrays: We zip
startTimes
andendTimes
to produce a list of tuples:1zippedTimes = [(1, 3), (2, 2), (3, 7)]
-
List Comprehension and Conditional Expressions: We use a list comprehension to iterate through
zippedTimes
and evaluate whetherqueryTime
falls within each student's interval:1homeworkStatus = [(1 <= 2 <= 3), (2 <= 2 <= 2), (3 <= 2 <= 7)]
This gives us:
1homeworkStatus = [True, True, False]
-
Summation of True Instances: Using the
sum
function, we count theTrue
values in thehomeworkStatus
list, which represent the students who were doing their homework at thequeryTime
:1busyStudents = sum([True, True, False])
This results in
busyStudents = 2
. -
Return the Count: The final result, which is
2
, is the answer to how many students were doing their homework atqueryTime
.
So, for our example, at queryTime = 2
, there were 2 students actively doing their homework. The one-liner corresponding to this process in the actual implementation would be:
1busyStudents = sum(a <= queryTime <= b for a, b in zip(startTimes, endTimes))
And when we insert our example values, the function call would be:
1busyStudents = sum(1 <= 2 <= 3, 2 <= 2 <= 2, 3 <= 2 <= 7) # Evaluates to 2
Thus, this simple and effective algorithm finds the solution with an elegant and concise approach.
Solution Implementation
1from typing import List
2
3class Solution:
4 def busy_student(self, start_time: List[int], end_time: List[int], query_time: int) -> int:
5 # Initialize the count of busy students.
6 busy_students_count = 0
7
8 # Iterate over paired start and end times using zip.
9 for start, end in zip(start_time, end_time):
10 # Check if the query_time is between any start and end time.
11 if start <= query_time <= end:
12 busy_students_count += 1 # If so, increment the count.
13
14 # Return the total count of busy students at query_time.
15 return busy_students_count
16
17# The function can be used as follows:
18# solution = Solution()
19# result = solution.busy_student([1, 2, 3], [3, 2, 7], 4)
20# print(result) # Output: 1
21
1class Solution {
2 // Method to count how many students are 'busy' at a given queryTime.
3 // A student is considered 'busy' if the queryTime falls between their startTime and endTime inclusive.
4 public int busyStudent(int[] startTimes, int[] endTimes, int queryTime) {
5 int busyCount = 0; // Counter for the number of busy students
6
7 // Iterate over the array of start times.
8 // Assuming startTimes and endTimes arrays are of the same length.
9 for (int i = 0; i < startTimes.length; i++) {
10 // Check if the queryTime is between the startTime and endTime for each student.
11 if (startTimes[i] <= queryTime && queryTime <= endTimes[i]) {
12 busyCount++; // Increment the count if the student is busy at queryTime.
13 }
14 }
15
16 // Return the total count of busy students.
17 return busyCount;
18 }
19}
20
1class Solution {
2public:
3 // Function that counts the number of students who are busy at a specific queryTime
4 int busyStudent(vector<int>& startTimes, vector<int>& endTimes, int queryTime) {
5 int count = 0; // Initialize the counter to 0
6
7 // Loop over all students
8 for (int i = 0; i < startTimes.size(); ++i) {
9 // If queryTime is between the startTime and endTime for a student, increase the count
10 if (startTimes[i] <= queryTime && queryTime <= endTimes[i]) {
11 count++;
12 }
13 }
14
15 // Return the total count of students who are busy at queryTime
16 return count;
17 }
18};
19
1// This function calculates the number of students who are busy at a given time.
2// @param {number[]} startTimes - The array of start times for student study sessions.
3// @param {number[]} endTimes - The array of end times for student study sessions.
4// @param {number} queryTime - The specific time at which we want to know how many students are busy.
5// @returns {number} - The count of students who are busy at the queryTime.
6function busyStudent(startTimes: number[], endTimes: number[], queryTime: number): number {
7 // Retrieve the total number of students by checking the length of the startTimes array.
8 const studentCount = startTimes.length;
9
10 // Initialize a variable to keep track of the number of busy students.
11 let busyCount = 0;
12
13 // Loop over each student's session times.
14 for (let i = 0; i < studentCount; i++) {
15 // If the current query time falls within the start and end times of a student's session,
16 // increment the count of busy students.
17 if (startTimes[i] <= queryTime && endTimes[i] >= queryTime) {
18 busyCount++;
19 }
20 }
21
22 // Return the total count of busy students at the query time.
23 return busyCount;
24}
25
Time and Space Complexity
Time Complexity:
The time complexity of the code is O(n)
, where n
is the number of students. This is because the code uses a generator expression within the sum
function that iterates over each student once to check if the queryTime
is between their startTime
and endTime
.
Each comparison a <= queryTime <= b
is done in constant time O(1)
, and since there are n
such comparisons (assuming startTime
and endTime
lists are both of length n
), the total time complexity of the loop is linear with respect to the number of students.
Space Complexity:
The space complexity of the code is O(1)
. The generator expression does not create an additional list in memory; it computes the sum on-the-fly, and thus there is no significant additional space usage that depends on the input size. The only space used is for the variables and the input lists themselves, which are not counted towards space complexity as they are considered to be input to the function.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.