Number of students

Photo by Xin Wang

This post is part of the Algorithms Problem Solving series.

Problem description

This is the number of students problem. The description looks like this:

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.

Examples

Input: startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
Output: 1

Input: startTime = [4], endTime = [4], queryTime = 4
Output: 1

Input: startTime = [4], endTime = [4], queryTime = 5
Output: 0

Input: startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7
Output: 0

Input: startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
Output: 5

Solution

The idea is just to iterate through the lists and compare them with the query_time to see if it is in the interval between start and end time. If it is, just increment the number_of_students counter. After the for loop finishes, return this value.

def busy_student(start_time, end_time, query_time):
    number_of_students = 0

    for index in range(len(start_time)):
        start, end = start_time[index], end_time[index]

        if query_time >= start and query_time <= end:
            number_of_students += 1

    return number_of_students

But we could also use the zip function to iterate through the list simultaneously:

def busy_student(start_time, end_time, query_time):
    number_of_students = 0

    for start, end in zip(start_time, end_time):
        if query_time >= start and query_time <= end:
            number_of_students += 1

    return number_of_students

The runtime complexity is O(N) where N is the number of integers in the start_time and end_time.

Resources

• Learning Python: From Zero to Hero
• Algorithms Problem Solving Series
• Stack Data Structure
• Queue Data Structure
• Linked List
• Tree Data Structure

Have fun, keep learning, and always keep coding!

My Twitter and Github