Points That Intersect With Cars

Problem Description

You are given a 0-indexed 2D integer array nums representing the coordinates of the cars parking on a number line. For any index i, nums[i] = [start_i, end_i] where start_i is the starting point of the ith car and end_i is the ending point of the ith car. Return the number of integer points on the line that are covered with any part of a car.

Key Insights

• Each car occupies a range of points on a number line from start_i to end_i.
• We need to count all unique integer points covered by any of the cars.
• Overlapping ranges mean that the same integer point may be counted multiple times, so we need to ensure unique counting.
• We can use a boolean array to track which points are covered by at least one car.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can use a boolean array to represent the points on the number line that can be covered by the cars. We iterate through the list of cars, marking the points in the boolean array that fall within the start and end positions of each car. Finally, we count the number of points that are marked as covered.

1. Initialize a boolean array covered of size 101 (to cover points 1 to 100).
2. For each car's start and end points, mark the corresponding indices in the covered array as True.
3. Count the number of True values in the covered array to get the result.

Code Solutions