Largest Rider Group Where Every Rider's Companion-Count Limits Hold

A car can take a group of riders on a shared trip. There are N riders, and each rider has two limits: rider i is willing to share the trip with at least low[i] and at most high[i] other riders. If k riders travel together, each of them shares the trip with exactly k - 1 others, so every chosen rider must satisfy low[i] <= k - 1 <= high[i].

Return the largest k for which some group of k riders satisfies every rider in the group. The interviewer required O(N) time.

Function Signature

def max_group_size(low: list[int], high: list[int]) -> int:

Rules

• Any subset of the riders may be chosen. Assume the car has room for all N riders, so the only limits are the riders' own.
• Riders who are not chosen impose no condition.
• If no group of one or more riders works, return 0.

Constraints

• 1 <= N <= 10^5, where N = len(low) == len(high)
• 0 <= low[i] <= high[i] <= 10^9
• Required time complexity: O(N).

Examples

Example 1

Input: low = [0, 1, 1, 2, 2]
 high = [1, 2, 2, 4, 4]
Output: 3

Riders 1, 2, 3 and 4 all accept exactly 2 others, so any three of them can travel together. A group of 4 would need every member to accept 3 others, and a group of 5 would need every member to accept 4 others; in both cases only riders 3 and 4 qualify.

Example 2

Input: low = [2, 2, 2, 0]
 high = [2, 2, 3, 0]
Output: 3

Riders 0, 1 and 2 each travel with exactly 2 others. A group of 4 fails because only rider 2 accepts 3 others. Rider 3 only travels alone, and no group of 2 works even though a group of 3 does.

Example 3

Input: low = [1, 2]
 high = [1, 3]
Output: 0

A single rider would need to accept 0 others, and neither does. A pair fails because rider 1 needs at least 2 others.