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:

1. Zipping the Arrays: The zip function takes two lists, startTime and endTime, 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).

2. 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), where a and b are the start and end times, respectively. This expression returns True if queryTime is within the inclusive range [a, b]; otherwise, it returns False.

3. Summation of True Instances: Python treats True as 1 and False as 0. The sum function is used to add up all the results of the conditional expressions within the list comprehension. Effectively, this adds up all 1s (whenever the condition is True), which corresponds to counting the number of students who are busy at queryTime.

4. Return the Count: The result of the sum is the total number of students doing their homework at the queryTime, 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.

Example 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:

1. Zipping the Arrays: We zip startTimes and endTimes to produce a list of tuples:

   1zippedTimes = [(1, 3), (2, 2), (3, 7)]

2. List Comprehension and Conditional Expressions: We use a list comprehension to iterate through zippedTimes and evaluate whether queryTime falls within each student's interval:

   1homeworkStatus = [(1 <= 2 <= 3), (2 <= 2 <= 2), (3 <= 2 <= 7)]

   This gives us:

   1homeworkStatus = [True, True, False]

3. Summation of True Instances: Using the sum function, we count the True values in the homeworkStatus list, which represent the students who were doing their homework at the queryTime:

   1busyStudents = sum([True, True, False])

   This results in busyStudents = 2.

4. Return the Count: The final result, which is 2, is the answer to how many students were doing their homework at queryTime.

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

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.