algoadvance

You are given an array cars where each cars[i] = [start_i, end_i] represents the start and the end points of the i-th car on an infinite number line.

Return the number of integer points on the line that are covered with **exactly one car**.

Example 1:

Input: cars = [[1,3],[3,5],[2,6]]
Output: 2
Explanation: 
The integer points in the ranges are:
[1, 2, 3] intersects with car 0.
[3, 4, 5] intersects with car 1.
[2, 3, 4, 5, 6] intersects with car 2.
Points covered with exactly one car: [1, 6], which are 2 points.

Example 2:

Input: cars = [[0,2],[2,4],[4,6]]
Output: 4
Explanation: 
The integer points in the ranges are:
[0, 1, 2] intersects with car 0.
[2, 3, 4] intersects with car 1.
[4, 5, 6] intersects with car 2.
Points covered with exactly one car: [0, 1, 3, 5], which are 4 points.

Clarifying Questions

1. Can cars share endpoints?
   • Yes, cars can share endpoints as shown in the given examples.
2. Are the given ranges inclusive of both start and end points?
   • Yes, the ranges are inclusive of both start and end points.

Strategy

1. Track Coverage Intervals:
   • Use a dictionary to track the number of cars covering each integer point.
2. Count Points Covered by Exactly One Car:
   • Iterate through the dictionary to count the number of points covered exactly once.

Code

def count_exactly_one_covered(cars):
    coverage = {}

    for start, end in cars:
        for point in range(start, end + 1):
            if point in coverage:
                coverage[point] += 1
            else:
                coverage[point] = 1

    count = 0
    for point in coverage:
        if coverage[point] == 1:
            count += 1

    return count

# Example 1
print(count_exactly_one_covered([[1, 3], [3, 5], [2, 6]]))  # Output: 2

# Example 2
print(count_exactly_one_covered([[0, 2], [2, 4], [4, 6]]))  # Output: 4

Time Complexity

• Building the Coverage Dictionary: This involves looping through each car’s range and populating the dictionary, resulting in O(n * k) time complexity, where n is the number of cars and k is the average length of each car’s range.
• Counting Points: Iterating through the dictionary keys takes O(m) time, where m is the number of unique points.

So, overall, the time complexity is O(n * k + m).

Try our interview co-pilot at AlgoAdvance.com

• 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?