Counting integers that are within intervals

Question

I am looking for a more efficient way than brute-forcing my way through in the following problem in python 3.

Problem statement:

Input:

• An array of n integers, scores, where each score is denoted by scores_j

• An array of q integers, lowerLimits, where each lowerLimits_i denotes the lower limit for score range i.

• An array of q integers, upper limits, where each upperLimits_i denotes the upper limit for score range i.

Output: A function that returns an array of Q integers where the value at each index I denotes the number of integers that are in the inclusive range [lowerLimits_i, upperLimits_i].

Constraints:

• 1 ≤ n ≤ 1e5
• 1 ≤ scores_j ≤ 1e9
• 1 ≤ q ≤ 1e5
• 1 ≤ lowerLimits_i ≤ upperLimits_i ≤ 1e9

Example: Given scores= [5, 8, 7], lowerLimits = [3, 7], and upperLimits = [9, 7] I want to check how many of the integers are contained in each interval (inclusive). In this examples: intervals are [3,9] and [7,7], and the result would be [3, 1].

My code looks like this:

def check(scores, lowerLimits, upperLimits):
   res = []
   for l, u in zip(lowerLimits, upperLimits):
       res.append(sum([l <= y <= u for y in scores]))
   return res
if __name__ == "__main__":
   scores= [5, 8, 7]
   lowerLimits = [3, 7]
   upperLimits = [9, 7]

   print(check(scores, lowerLimits, upperLimits))

Answer 1

Am not sure as this would give a better TC but still what you can try is

First, sort the values
Second, iterate over the sorted list and find the lower hand limit and keep a count till the upper limit
That how you get the count of all the values and the remaining values that are not in the range can be discarded.