Busy Intersection Leetcode Solved

Given a list of cars traveling from point start to end with speed in the format [start, end, speed]. You need to return the list of smallest intervals (segments) and the average speed of vehicles in each of those intervals.

Used for road color coding as per traffic prediction used in google maps or lately uber.

The problem involves processing a list of cars that are traveling from a starting point to an ending point with a given speed, and then returning the list of smallest intervals (segments) and the average speed of vehicles in each of those intervals.

This problem involves sorting and calculating prefix sums, which are techniques commonly used in array manipulation problems.

To solve this problem, we can follow the following steps:

1. Sort the list of cars by their starting points.
2. Initialize a variable ‘current_end’ to the starting point of the first car in the sorted list, and a variable ‘current_total_speed’ to the speed of the first car.
3. Initialize a variable ‘current_count’ to 1, since there is at least one car in the current interval.
4. Initialize an empty list ‘intervals’ to hold the resulting intervals and their average speeds.
5. For each car in the sorted list: a. If the current car’s starting point is less than or equal to the current end point, it means that the current car is part of the current interval. Add its speed to ‘current_total_speed’, and increment ‘current_count’. b. If the current car’s starting point is greater than the current end point, it means that we have reached the end of the current interval. Calculate the average speed of the current interval as ‘current_total_speed’ divided by ‘current_count’, and append the current interval and its average speed to the ‘intervals’ list. c. Update ‘current_end’ to the current car’s ending point, and ‘current_total_speed’ to the current car’s speed. d. Reset ‘current_count’ to 1, since we are starting a new interval.
6. After processing all cars in the sorted list, calculate the average speed of the last interval and append it to the ‘intervals’ list.
7. Return the ‘intervals’ list.

Here is an example to illustrate how this algorithm works:

Input: [[0, 5, 50], [3, 10, 80], [4, 8, 60], [12, 15, 70], [16, 20, 90]]

Output: [[0, 5, 52.5], [5, 12, 73.33], [12, 15, 70], [15, 20, 90]]

Explanation:

• The first car starts at point 0 and ends at point 5 with a speed of 50.
• The second car starts at point 3 and ends at point 10 with a speed of 80. Since its starting point is within the current interval (0-5), it is part of the current interval. The current interval’s total speed is 50 + 80 = 130, and the current count is 2.
• The third car starts at point 4 and ends at point 8 with a speed of 60. Since its starting point is within the current interval (0-5), it is also part of the current interval. The current interval’s total speed is 50 + 80 + 60 = 190, and the current count is 3.
• The fourth car starts at point 12 and ends at point 15 with a speed of 70. Since its starting point is greater than the current end point (5), it means that we have reached the end of the current interval. The current interval’s average speed is 190 / 3 = 63.33, and we append the interval [0, 5, 52.5] to the ‘intervals’ list.
• We update ‘current_end’ to 10, ‘current_total_speed’ to 80, and ‘current_count’ to 1

Solution 1: Using a nested loop

In this solution, we iterate over each interval and then iterate over each car to find which cars fall within that interval. We keep track of the sum of speeds and the count of cars within each interval to calculate the average speed.

Step-by-step solution

1. Sort the list of cars by their starting points.
2. Initialize an empty list ‘intervals’ to hold the resulting intervals and their average speeds.
3. For each interval: a. Initialize variables ‘total_speed’ and ‘car_count’ to 0. b. For each car in the list: i. If the car is within the interval, add its speed to ‘total_speed’ and increment ‘car_count’. c. Calculate the average speed of the cars in the interval as ‘total_speed’ divided by ‘car_count’. d. Append the interval and its average speed to the ‘intervals’ list.
4. Return the ‘intervals’ list.

Time Complexity: O(n^2), where n is the length of the input list of cars. This is because we need to iterate over each interval and each car in the list.

Space Complexity: O(n), where n is the length of the input list of cars. This is because we need to store the intervals and their average speeds in the ‘intervals’ list.

Solution 2: Using a sliding window

In this solution, we use a sliding window approach to keep track of the cars within each interval. We initialize a window at the starting point of the first car and slide it over to the ending point of each car, adding the speed of each car to the total speed and incrementing the car count for each car that falls within the window. We calculate the average speed at the end of each interval.

Step-by-step solution

1. Sort the list of cars by their starting points.
2. Initialize an empty list ‘intervals’ to hold the resulting intervals and their average speeds.
3. Initialize variables ‘start’ and ‘end’ to the starting and ending points of the first car in the list, and ‘total_speed’ and ‘car_count’ to the speed and count of the first car.
4. For each car in the list: a. If the car’s starting point is less than or equal to the current window’s ending point, it means that the car is part of the current interval. Add its speed to ‘total_speed’ and increment ‘car_count’. b. If the car’s starting point is greater than the current window’s ending point, it means that we have reached the end of the current interval. Calculate the average speed of the cars in the current interval as ‘total_speed’ divided by ‘car_count’, and append the interval and its average speed to the ‘intervals’ list. i. Update ‘start’ to the starting point of the current car. ii. Update ‘end’ to the ending point of the current car. iii. Update ‘total_speed’ to the speed of the current car. iv. Reset ‘car_count’ to 1.
5. Calculate the average speed of the last interval and append it to the ‘intervals’ list.
6. Return the ‘intervals’ list.

Time Complexity: O(nlogn), where n is the length of the input list of cars. This is because we need to sort the list of cars by their starting points, which takes O(nlogn) time. The sliding window approach takes O(n) time.

Space Complexity: O(n), where n is the length of the input list of cars.

Solution 3: Using prefix sums

In this solution, we use prefix sums to calculate the total speed of the cars within each interval. We create a prefix sum array where each element represents the total speed of the cars up to that point in the list. We can then calculate the total speed of the cars within an interval by taking the difference between the prefix sums at the ending point and starting point of the interval. We divide this by the number of cars within the interval to calculate the average speed.

Step-by-step solution

1. Sort the list of cars by their starting points.
2. Initialize an empty list ‘intervals’ to hold the resulting intervals and their average speeds.
3. Initialize a prefix sum array ‘prefix_sum’ to hold the total speeds of cars up to each car in the list. a. Calculate the total speed of the first car and set prefix_sum[0] to this value. b. For each subsequent car, add its speed to the previous element in the prefix sum array to calculate the total speed up to that point.
4. For each interval: a. Calculate the total speed of the cars within the interval by taking the difference between the prefix sums at the ending point and starting point of the interval. b. Calculate the average speed of the cars in the interval by dividing the total speed by the number of cars within the interval. c. Append the interval and its average speed to the ‘intervals’ list.
5. Return the ‘intervals’ list.

Time Complexity: O(nlogn), where n is the length of the input list of cars. This is because we need to sort the list of cars by their starting points, which takes O(nlogn) time. Creating the prefix sum array takes O(n) time, and calculating the total speed of the cars within each interval takes O(1) time.

Space Complexity: O(n), where n is the length of the input list of cars. This is because we need to store the prefix sum array and the intervals and their average speeds in the ‘intervals’ list.

Which solution should I go with?

For interview preparation, it’s usually best to choose the solution that strikes a balance between efficiency and simplicity. In this case, the sliding window approach is likely the best choice.

It has a time complexity of O(nlogn) and a space complexity of O(n), which are both relatively efficient, and it’s a straightforward algorithm that is easy to understand and implement.

The prefix sum approach also has a similar time complexity but a higher space complexity, so it may be more difficult to implement correctly in an interview setting. The nested loop approach, while simple, has a higher time complexity of O(n^2), which may be too slow for larger input sizes.

Python Solution for Busy Intersection

def busy_intersection(cars):
    cars.sort(key=lambda x: x[0])  # Sort by starting point
    
    n = len(cars)
    prefix_sum = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_sum[i] = prefix_sum[i - 1] + cars[i - 1][2]  # Calculate prefix sums
    
    intervals = []
    start, end = cars[0][0], cars[0][1]
    total_speed, car_count = prefix_sum[1], 1
    for i in range(1, n):
        if cars[i][0] <= end:  # Car is within current interval
            total_speed += prefix_sum[i + 1] - prefix_sum[i]
            car_count += 1
        else:  # New interval
            interval_speed = total_speed / car_count
            intervals.append([start, end, interval_speed])
            start, end = cars[i][0], cars[i][1]
            total_speed, car_count = cars[i][2], 1
    
    interval_speed = total_speed / car_count
    intervals.append([start, end, interval_speed])  # Add last interval
    
    return intervals

Java Solution for Busy Intersection

public List<double[]> busyIntersection(int[][] cars) {
    Arrays.sort(cars, (a, b) -> a[0] - b[0]);  // Sort by starting point
    
    int n = cars.length;
    double[] prefixSum = new double[n + 1];
    for (int i = 1; i <= n; i++) {
        prefixSum[i] = prefixSum[i - 1] + cars[i - 1][2];  // Calculate prefix sums
    }
    
    List<double[]> intervals = new ArrayList<>();
    int start = cars[0][0], end = cars[0][1];
    double totalSpeed = prefixSum[1], carCount = 1;
    for (int i = 1; i < n; i++) {
        if (cars[i][0] <= end) {  // Car is within current interval
            totalSpeed += prefixSum[i + 1] - prefixSum[i];
            carCount++;
        } else {  // New interval
            double intervalSpeed = totalSpeed / carCount;
            intervals.add(new double[] {start, end, intervalSpeed});
            start = cars[i][0];
            end = cars[i][1];
            totalSpeed = cars[i][2];
            carCount = 1;
        }
    }
    
    double intervalSpeed = totalSpeed / carCount;
    intervals.add(new double[] {start, end, intervalSpeed});  // Add last interval
    
    return intervals;
}

JavaScript Solution for Busy Intersection

function busyIntersection(cars) {
    cars.sort((a, b) => a[0] - b[0]);  // Sort by starting point
    
    const n = cars.length;
    const prefixSum = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        prefixSum[i] = prefixSum[i - 1] + cars[i - 1][2];  // Calculate prefix sums
    }
    
    const intervals = [];
    let start = cars[0][0], end = cars[0][1];
    let totalSpeed = prefixSum[1], carCount = 1;
    for (let i = 1; i < n; i++) {
        if (cars[i][0] <= end) {  // Car is within current interval
            totalSpeed += prefixSum[i + 1] - prefixSum[i];
            carCount++;
        } else {  // New interval
            const intervalSpeed = totalSpeed / carCount;
            intervals.push([start, end, intervalSpeed]);
            start = cars[i][0];
            end = cars[i][1];
            totalSpeed = cars[i][2];
            carCount = 1;
        }
    }
    
    const intervalSpeed = totalSpeed / carCount;
    intervals.push([start, end, intervalSpeed]);  // Add last interval
    
    return intervals;
}

Ruby Solution for Busy Intersection

def busy_intersection(cars)
    cars.sort_by! { |car| car[0] }  # Sort by starting point
    
    n = cars.length
    prefix_sum = Array.new(n + 1, 0)
    (1..n).each do |i|
        prefix_sum[i] = prefix_sum[i - 1] + cars[i - 1][2]  # Calculate prefix sums
    end
    
    intervals = []
    start, finish = cars[0][0], cars[0][1]
    total_speed, car_count = prefix_sum[1], 1
    (1...n).each do |i|
        if cars[i][0] <= finish  # Car is within current interval
            total_speed += prefix_sum[i + 1] - prefix_sum[i]
            car_count += 1
        else  # New interval
            interval_speed = total_speed / car_count
            intervals << [start, finish, interval_speed]
            start, finish = cars[i][0], cars[i][1]
            total_speed, car_count = cars[i][2], 1
        end
    end
    
    interval_speed = total_speed / car_count
    intervals << [start, finish, interval_speed]  # Add last interval
    
    intervals
end