# Number of Students Doing Homework at a Given Time **Difficulty:** EASY [External](https://leetcode.com/problems/number-of-students-doing-homework-at-a-given-time) Canonical: https://scaleengineer.com/dsa/problems/number-of-students-doing-homework-at-a-given-time **Data structures:** Array --- ## Problem 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.length` * `1 <= startTime.length <= 100` * `1 <= startTime[i] <= endTime[i] <= 1000` * `1 <= queryTime <= 1000` # Approaches ## Line Sweep / Difference Array This approach uses a technique known as a difference array or line sweep. It's particularly useful when you need to answer multiple queries about the number of active intervals at different points in time. We create a timeline array to mark the start and end points of each student's homework session. By processing these start and end events, we can determine the number of active students at any given time. **Time:** O(n + T_max), where `n` is the number of students and `T_max` is the maximum time. O(n) to iterate through all students and O(T_max) to compute the prefix sum up to `queryTime`. · **Space:** O(T_max), where T_max is the maximum possible value for time (1000 in this case). We need an auxiliary array to store the timeline events. **Pros:** Extremely efficient if the problem involved multiple queries. After a one-time preprocessing step (O(n + T_max)), each query could be answered in O(1) time. **Cons:** For a single query, this approach has a higher time complexity (O(n + T_max)) compared to a simple loop (O(n)).; It requires extra space proportional to the maximum possible time (O(T_max)), which is less memory-efficient than the O(1) space approach. ### Explanation The core idea is to represent the changes in the number of active students on a timeline. Instead of tracking the count for every single time unit, we only mark the points where the count changes. 1. We initialize an array, let's call it `timeline`, of a size slightly larger than the maximum possible time (e.g., 1002, since max time is 1000). This array is filled with zeros. 2. We iterate through each student's homework interval `[startTime[i], endTime[i]]`. 3. For each student, we increment the value at `timeline[startTime[i]]`. This marks that at `startTime[i]`, the number of busy students increases by one. 4. We then decrement the value at `timeline[endTime[i] + 1]`. This marks that at the time unit just after `endTime[i]`, the number of busy students decreases by one. 5. After marking all start and end events, we can find the number of students at `queryTime` by calculating the running sum of the `timeline` array up to that point. We iterate from time `t = 0` to `queryTime`, accumulating the values in the `timeline` array. The final sum is our answer. ```java class Solution { public int busyStudent(int[] startTime, int[] endTime, int queryTime) { // Max time is 1000, so we need an array of size 1002 for endTime[i] + 1 int[] timeline = new int[1002]; // Mark the start and end points for (int i = 0; i < startTime.length; i++) { timeline[startTime[i]]++; if (endTime[i] + 1 < timeline.length) { timeline[endTime[i] + 1]--; } } // Calculate the number of students at queryTime by taking the prefix sum int activeStudents = 0; for (int i = 0; i <= queryTime; i++) { activeStudents += timeline[i]; } return activeStudents; } } ``` ### Algorithm - Create an integer array `timeline` of a size larger than the maximum possible time (e.g., 1002), initialized to all zeros. - For each student `i`, increment the count at the start time index: `timeline[startTime[i]]++`. - For each student `i`, decrement the count at the index immediately after the end time: `timeline[endTime[i] + 1]--`. - Calculate the prefix sum of the `timeline` array up to `queryTime`. This is done by iterating from time 0 to `queryTime` and accumulating the values. - The accumulated sum at `queryTime` is the number of students doing homework at that specific time. ## Simple Iteration This is the most straightforward and optimal approach for this problem, given the constraints. We can simply iterate through each student and check if the given `queryTime` falls within their homework interval `[startTime[i], endTime[i]]`. **Time:** O(n), where `n` is the number of students (`startTime.length`). We need to iterate through each student once to check their interval. · **Space:** O(1), as we only use a single counter variable and a loop index. The space used does not scale with the size of the input arrays. **Pros:** Optimal time complexity for a single query.; Optimal space complexity as it uses no extra space proportional to the input size.; Simple to understand and implement. **Cons:** If the problem were modified to handle a large number of queries, this approach would be inefficient as it would re-calculate the result from scratch for each query. ### Explanation The logic is to directly check the condition for each student one by one. We maintain a count of students who satisfy the condition. We start with a counter initialized to zero. Then, we loop through all the students. For each student, we access their `startTime` and `endTime`. We then perform a simple check: is the `queryTime` greater than or equal to the student's `startTime` and less than or equal to their `endTime`? If this condition holds true, it means the student was doing their homework at the `queryTime`, so we increment our counter. After iterating through all the students, the counter will hold the total number of students who were busy at `queryTime`, and we return this value. ```java class Solution { public int busyStudent(int[] startTime, int[] endTime, int queryTime) { int busyStudentCount = 0; for (int i = 0; i < startTime.length; i++) { if (startTime[i] <= queryTime && queryTime <= endTime[i]) { busyStudentCount++; } } return busyStudentCount; } } ``` ### Algorithm - Initialize a counter variable, `busyStudentCount`, to 0. - Iterate through each student from `i = 0` to `n-1`, where `n` is the number of students. - For each student, check if the `queryTime` is within their homework interval. The condition is `startTime[i] <= queryTime && queryTime <= endTime[i]`. - If the condition is true, increment `busyStudentCount`. - After the loop completes, return `busyStudentCount`. # Solutions ### Java ```java class Solution { public int busyStudent(int[] startTime, int[] endTime, int queryTime) { int ans = 0; for (int i = 0; i < startTime.length; ++i) { if (startTime[i] <= queryTime && queryTime <= endTime[i]) { ++ans; } } return ans; } } ``` ### CPP ```cpp class Solution { public: int busyStudent(vector &startTime, vector &endTime, int queryTime) { int ans = 0; for (int i = 0; i < startTime.size(); ++i) { ans += startTime[i] <= queryTime && queryTime <= endTime[i]; } return ans; } }; ``` ### Python ```python class Solution: def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int: return sum( a <= queryTime <= b for a, b in zip(startTime, endTime)) ```