algoadvance

Leetcode 1450. Number of Students Doing Homework at a Given Time

Problem Statement

You are given two integer arrays startTime and endTime and an integer queryTime.

The i-th 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 the queryTime. More formally, return the number of students where queryTime lays in the interval [startTime[i], endTime[i]] inclusive.

Example:

1. Example 1:
   • Input:
     • startTime = [1,2,3]
     • endTime = [3,2,7]
     • queryTime = 4
   • Output: 1
   • Explanation: Only the third student was doing their homework at the time 4.
2. Example 2:
   • Input:
     • startTime = [4]
     • endTime = [4]
     • queryTime = 4
   • Output: 1
   • Explanation: The only student was doing their homework at the time 4.

Clarifying Questions

1. Range of Inputs:
   • What are the constraints on the size of the arrays and the values within them?
   • Constraints:
     • startTime.length == endTime.length
     • 1 <= startTime.length <= 100
     • 1 <= startTime[i] <= endTime[i] <= 1000
     • 1 <= queryTime <= 1000
2. Edge Cases:
   • What if no students are found doing homework at queryTime?
     • The function should return 0 if no students are found doing homework at queryTime.

Strategy

1. Initialization:
   • Initialize a counter to keep track of the number of students doing homework at queryTime.
2. Iteration:
   • Iterate over the students (i.e., iterate over the arrays).
   • For each student, check if queryTime lies within the interval [startTime[i], endTime[i]].
   • If it does, increment the counter.
3. Return the Counter:
   • After iterating through all students, return the counter.

Code

#include <vector>

int busyStudent(std::vector<int>& startTime, std::vector<int>& endTime, int queryTime) {
    int count = 0;
    int n = startTime.size();
    
    for (int i = 0; i < n; ++i) {
        if (startTime[i] <= queryTime && queryTime <= endTime[i]) {
            count++;
        }
    }
    
    return count;
}

Explanation

• Initialize count to 0: This will keep track of the number of students working at queryTime.
• Loop through each student’s start and end times:
  • For each student i, check if startTime[i] is less than or equal to queryTime and endTime[i] is greater than or equal to queryTime.
  • If both these conditions are true, the student is doing homework during the queryTime, so increment the count.
• Return count: After checking all students, return the final count.

Time Complexity

• The time complexity of this solution is O(n), where n is the length of the startTime or endTime array.
• This linear time complexity is efficient given the constraint that startTime.length can be at most 100.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?