Katkat
Back

Maximize the Eligible Carpool Group

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to use a sweep-line algorithm or difference array to find the optimal point to maximize the number of overlapping intervals, subject to specific constraints.

Problem Statement

You are building a matching service for carpoolers. Each potential rider i is willing to join a group only if the total number of people in the car (including the driver) is at least min_size[i] and at most max_size[i].

Given a list of n riders where each rider is represented as a pair [min_size[i], max_size[i]], find a group size k (where 1 <= k <= 100,000) that maximizes the number of eligible riders. If multiple sizes yield the same maximum, return the smallest such k.

Function Signature

def find_optimal_group_size(riders: List[List[int]]) -> int:

Examples

Example 1: Input: riders = [[2, 4], [3, 5], [1, 2]] Output: 2 Explanation:

  • Size 1: Only rider 3 is eligible (Total: 1).
  • Size 2: Riders 1 and 3 are eligible (Total: 2).
  • Size 3: Riders 1 and 2 are eligible (Total: 2).
  • Size 4: Riders 1 and 2 are eligible (Total: 2).
  • Size 5: Only rider 2 is eligible (Total: 1). Since 2, 3, and 4 all result in 2 riders, we return the smallest: 2.

Constraints

  • 1 <= n <= 100,000
  • 1 <= min_size[i] <= max_size[i] <= 100,000

Edge Cases

  • Empty list of riders: return 0.
  • All intervals disjoint: return the start of the first interval.

Hints

Hint 1

Treat each rider's preference as an interval [min, max] that covers a range of possible group sizes.

Hint 2

Use a difference array (or sweep-line approach) to increment the count at `min_size` and decrement it after `max_size`.

Hint 3

After computing the prefix sums of the difference array, iterate through the results to find the index with the maximum value.

Follow-up questions

  • How would your approach change if the constraints on max_size were much larger (e.g., up to 10^9), while n remains 100,000?
  • What if we need to minimize the group size if there's a tie, but prioritize groups that include a specific VIP rider?
  • How would you modify the solution if every rider also had a weight (e.g., fare value) and you wanted to maximize the total fare collected?