DEV Community

loading...
Cover image for Algorithms Problem Solving: Number of students

Algorithms Problem Solving: Number of students

TK
Sharing knowledge https://leandrotk.github.io
Originally published at leandrotk.github.io ・2 min read

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

Resources

Discussion (0)