Ride-Sharing Service: Efficient Batching

Imagine you're developing a core feature for a ride-sharing service, similar to Uber Pool, where the goal is to efficiently group individual ride requests into compatible batches. The objective is to minimize the total number of vehicles required by maximizing the number of compatible riders grouped into each vehicle, while respecting batch size limits.

Each incoming ride request provides essential details. Your task is to identify and form groups (batches) of rides, with a maximum of 3 rides per batch, that can be served together based on compatibility criteria.

Ride Data Format:

Each ride is represented as a list of three strings: {"ride_id", "pickup_location", "pickup_time"}

Where:

Compatibility Rules:

Two or more rides are considered compatible and can be grouped into the same batch if, and only if:

Batching Constraints:

Output Ordering:

The final list of batches should be ordered based on the earliest original input index of any ride within that batch. For example, if a batch contains rides that were originally at index 0 and index 5 in the input list, and another batch contains rides from index 1 and index 2, the batch containing the ride from index 0 would appear first.

Note: The batches are ordered by the earliest input index: [1,2] (index 0), [3,5] (index 2), [4] (index 3), [6] (index 5).

Your Task:Implement a function that takes the list of ride requests as input and returns the final list of batches according to the rules and output ordering specified above.