Python 1450.py
class Solution:
def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:
startTime.sort()
endTime .sort()
a = bisect_right(startTime, queryTime)
b = bisect_left (endTime, queryTime)
return a - b
Difficulty
and has an acceptance rate of about 76% (200k+ submissions).
Typical patterns to solve this problem:
- Array
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a class Solution with a method busyStudent. The method receives three arguments: two integer lists startTime and endTime that represent the start and end moments of a set of students’ classes, and an integer queryTime that denotes a specific moment of interest. The goal of the method is to compute how many students are attending a class at exactly queryTime. The algorithm follows a sorting-and-binary-search strategy to achieve this efficiently.
Key Steps
The method proceeds through a small number of distinct operations, each of which is essential to the final count.
Sorting the input arrays
startTime.sort()
endTime.sort()
Both startTime and endTime are sorted in place. Sorting establishes a monotonic order that enables binary search operations later in the method. The sorted arrays serve as the basis for determining how many intervals have begun and how many have already finished relative to queryTime.
Counting started intervals with bisect_right
a = bisect_right(startTime, queryTime)
bisect_right returns the index of the first element in startTime that is greater than queryTime. Because the list is sorted, this index also equals the number of start times that are less than or equal to queryTime. In other words, a represents how many students have begun their class at or before the query moment.
Counting finished intervals with bisect_left
b = bisect_left(endTime, queryTime)
bisect_left yields the index of the first element in endTime that is not less than queryTime. Consequently, b counts how many end times are strictly less than queryTime. These are the students whose classes have already concluded before the query moment.
Deriving the final answer
return a - b
Subtracting the number of finished intervals (b) from the number of started intervals (a) yields the exact count of students whose class interval encloses queryTime. This arithmetic directly reflects the set difference between the two groups.
Edge Cases Handled
The algorithm gracefully handles several boundary conditions without additional code.
When queryTime is smaller than every start time, bisect_right returns zero, indicating that no class has started. Simultaneously, bisect_left also returns zero because no end time is less than queryTime. The subtraction yields zero, correctly indicating that no student is busy.
When queryTime exceeds all end times, bisect_right returns the length of startTime (all classes have started) while bisect_left returns the length of endTime (all classes have ended). Their difference is zero, reflecting that no class is ongoing at that moment.
If a class starts and ends at the same moment equal to queryTime, the start time is counted by bisect_right because it is “less than or equal to” the query, while the end time is not counted by bisect_left because the end time is not “less than” the query. The net effect is that such a zero-duration class is considered active at queryTime, matching the typical inclusive-start, exclusive-end interpretation used in interval counting.
When the input lists contain duplicate start or end times, the binary search functions correctly aggregate all occurrences. For duplicate start times equal to queryTime, bisect_right includes every duplicate, ensuring that all corresponding students are counted as having started. For duplicate end times equal to queryTime, bisect_left excludes them, preserving the inclusive-start, exclusive-end semantics.
Performance Optimizations
The primary optimization stems from replacing a naïve linear scan with binary search on sorted arrays. By sorting the two lists once and then performing two logarithmic lookups, the method reduces the overall work from O(n × m) in a double-loop scenario to O(n log n) for the sorting phase plus O(log n) for each binary search.
In-place sorting (list.sort()) avoids the allocation of additional data structures, thereby conserving memory and improving cache locality. The use of the standard library’s bisect module ensures that the binary search is implemented in highly optimized C code, which runs faster than a pure-Python loop.
Finally, the arithmetic subtraction (a - b) is a constant-time operation that combines the two search results without any further iteration, delivering the answer with minimal overhead.
ELI5 - Simplified Explanation
Imagine there is a big classroom filled with students. Each student has a block of time when they are busy working on their homework. Some start early and finish late, while others start and finish very quickly. You want to know how many students are working at one specific moment that you choose.
Think of the starting times as a line of clocks and the finishing times as another line of clocks. Sorting the lists is like putting all the start times in order from the smallest number to the largest number, and doing the same thing for the end times.
When you look for the moment you care about, the code finds how many students have already started their work by looking at the start times. Then, it finds how many students have already finished their work by looking at the end times. By subtracting the number of students who are already done from the total number of students who have started, you are left with just the ones who are still sitting at their desks working during that exact moment.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | ||||||
| WalkCCC | C++ | ||||||||||
| leetcode.ca | C++ | Python | Java | Go | C | Rust | TS | ||||
| Progiez | C++ | Python | Java | ||||||||
| github | BigEggStudy | C# | |||||||||
| black-shadows | C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| fartem | Ruby | ||||||||||
| fsq | C++ | ||||||||||
| JoshCrozier | JS | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| muhammadfarhankt | Go | ||||||||||
| suxrobGM | C# | ||||||||||
| trung-hn | Python | ||||||||||
| varunu28 | Java | ||||||||||
| YuriSpiridonov | Python | ||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||
| WalkCCC | C++ | ||||||||||
| leetcode.ca | C, C++, Go, Java, Python, Rust, TypeScript | ||||||||||
| Progiez | C++, Java, Python | ||||||||||
| BigEggStudy | C# | ||||||||||
| black-shadows | C++, C++ | ||||||||||
| charles-wangkai | Java | ||||||||||
| DimitrisJim | C | ||||||||||
| fartem | Ruby | ||||||||||
| fsq | C++ | ||||||||||
| JoshCrozier | JavaScript | ||||||||||
| keineahnung2345 | C++ | ||||||||||
| lkwq007 | Python | ||||||||||
| muhammadfarhankt | Go | ||||||||||
| suxrobGM | C# | ||||||||||
| trung-hn | Python | ||||||||||
| varunu28 | Java | ||||||||||
| YuriSpiridonov | Python |
Videos
Solved On The Same Day
- problem 1436: Destination City
- problem 1446: Consecutive Characters
- problem 1423: Maximum Points You Can Obtain from Cards
- problem 1432: Max Difference You Can Get From Changing an Integer
- problem 1433: Check If a String Can Break Another String
- problem 1447: Simplified Fractions
- problem 1451: Rearrange Words in a Sentence
- problem 1452: People Whose List of Favorite Companies Is Not a Subset of Another List
- problem 1483: Kth Ancestor of a Tree Node
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality