223. Maximum Comfortable Riders in a Car

Maximum Comfortable Riders in a Car

You are given n riders and one car with unlimited space. Each rider has a comfort range for how many other riders must be present in the car.

A rider will ride only if the number of other riders in the car is within their comfort range. Return the maximum number of riders that can ride together in the car.

Each comfort range is represented as a string "minOther,maxOther", where minOther is the minimum number of other riders required and maxOther is the maximum number of other riders allowed.

Method Signature

int maximumRiders(List<String> comfortableRanges)

Parameters

comfortableRanges: a list of rider comfort ranges. n = comfortableRanges.size()
Each string is in the format "minOther,maxOther".
For rider i, the rider can ride only if the number of other riders is between minOther and maxOther, inclusive.

Returns

Return the maximum number of riders that can ride together.
If no non-empty group of riders can satisfy the condition, return 0.

Rules

If total riders in the car is x, then every selected rider sees x - 1 other riders.
A rider with range "minOther,maxOther" can be selected only if minOther ≤ x - 1 ≤ maxOther.
The answer must be deterministic and must return only the maximum possible count.

Constraints

1 ≤ comfortableRanges.size() ≤ 200,000
0 ≤ minOther ≤ maxOther < comfortableRanges.size()
Each string in comfortableRanges contains exactly two comma-separated integers.

Examples

Example 1

maximumRiders(comfortableRanges = List.of("0,1", "1,3", "1,2", "2,4", "3,4"))

Output: 3

Explanation: If 3 riders sit in the car, each selected rider sees 2 other riders. Riders with ranges "1,3", "1,2", and "2,4" can ride together.

Example 2

maximumRiders(comfortableRanges = List.of("0,0", "0,2", "1,2", "2,3"))

Output: 3

Explanation: If 3 riders sit in the car, each selected rider sees 2 other riders. Three riders have comfort ranges that allow 2 other riders.

Example 3

maximumRiders(comfortableRanges = List.of("1,2", "2,3", "3,3"))

Output: 0

Explanation:

If 1 rider sits in the car, that rider sees 0 other riders. No rider is comfortable with 0 other riders.
If 2 riders sit in the car, each selected rider sees 1 other rider. Only the rider with range "1,2" is comfortable, but 2 riders are required.
If 3 riders sit in the car, each selected rider sees 2 other riders. Riders with ranges "1,2" and "2,3" are comfortable, but 3 riders are required.

Therefore, no non-empty group of riders can satisfy the condition, so the answer is 0.