We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Points That Intersect With Cars

Number: 3034

Difficulty: Easy

Paid? No

Companies: Uber

Problem Description

Given a list of intervals nums where each interval represents the starting and ending points of a car parked on a number line, return the total number of distinct integer points that are covered by one or more intervals.

Key Insights

  • The problem is essentially about finding the union of all given intervals.
  • Merging overlapping intervals avoids double-counting integer points.
  • Given the constraint (points up to 100), even a brute force counting would work, but merging intervals is a cleaner approach.
  • Sorting intervals by their start value simplifies the merging process.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the intervals. Space Complexity: O(n) for storing the merged intervals.

Solution

The solution uses the following approach:

  1. Sort the intervals based on the start value.
  2. Iterate through the sorted intervals and merge them if they overlap (i.e., the current interval's start is less than or equal to the previous interval's end).
  3. For each merged interval, calculate the number of integer points it covers by using the formula (end - start + 1).
  4. Sum up the counts from all merged intervals to get the final result.

Data structures used:

  • An array (or list) to store the merged intervals.
  • Sorting simplifies the identification of overlapping intervals.

This approach ensures that each point is counted only once even if it is covered by multiple intervals.

Code Solutions

# Python solution
def countIntersectionPoints(nums):
    # Sort intervals based on their start values
    nums.sort(key=lambda interval: interval[0])
    merged_intervals = []
    
    for interval in nums:
        # If there is no interval in merged_intervals or if current interval doesn't overlap with the last one, add it.
        if not merged_intervals or merged_intervals[-1][1] < interval[0]:
            merged_intervals.append(interval)
        else:
            # Merge interval with the last interval in merged_intervals.
            merged_intervals[-1][1] = max(merged_intervals[-1][1], interval[1])
    
    # Calculate total points covered by merged intervals.
    total_points = 0
    for start, end in merged_intervals:
        total_points += (end - start + 1)
    
    return total_points

# Example usage:
nums = [[3,6],[1,5],[4,7]]
print(countIntersectionPoints(nums))  # Output: 7
← Back to All Questions