Count the number of values covered by all ranges | Tech Screen | Squarespace

Question

You are given an array of integers "values". Another array "ranges" has each element as a 2-list - [start, end] where "start" and "end" denote a range (start is always < end). Find the number of elements in "values" which are covered by every range (inclusive).

For eg, values = [2, 5, 13, 7, 17] ranges = [[2, 10], [2, 5], [1, 17]]

Answer = 2 because only values 2 and 5 are covered by every range.

Solution:

We need to find the intersection of all intervals in the ranges array to create a single interval. Those values which are covered by this single interval will count to our result:

def count_values_in_all_ranges(values, ranges) -> int:
    # Intersection of all inclusive ranges
    L = float("-inf")
    R = float("inf")

    for s, e in ranges:
        L = max(L, s)
        R = min(R, e)

    if L > R: # if no valid intersection exists
        return 0

    # Count values covered by the final intersection interval
    return sum(1 for v in values if L <= v <= R)