322. Climbers For Mountain Expedition

Climbers For Mountain Expedition

A mountaineering club wants to select the largest possible group from n climbers. The climbers have distinct experience levels from 1 to n, where climber 1 is the least experienced and climber n is the most experienced.

Each climber has limits on how many less-experienced and more-experienced climbers they are willing to join.

Climber i accepts at most lessExperienced[i] selected climbers with lower experience.
Climber i accepts at most moreExperienced[i] selected climbers with higher experience.

Find the maximum number of climbers that can be selected such that every selected climber's limits are satisfied.

Method Signature

int maximumExpeditionSize(List<Integer> lessExperienced, List<Integer> moreExperienced)

lessExperienced.get(i) is the maximum number of selected climbers with lower experience that climber i + 1 accepts.
moreExperienced.get(i) is the maximum number of selected climbers with higher experience that climber i + 1 accepts.
The method returns the maximum possible number of climbers in a valid expedition.

Selection Rules

The climbers' experience order cannot be changed.
Any subset of the available climbers may be selected.
Every selected climber must satisfy both their less-experienced and more-experienced limits.
Only the maximum expedition size must be returned, so the output is deterministic.

Constraints

1 ≤ lessExperienced.size() ≤ 200,000
lessExperienced.size() = moreExperienced.size()
0 ≤ lessExperienced.get(i) < lessExperienced.size()
0 ≤ moreExperienced.get(i) < moreExperienced.size()

Examples

Example 1

Method Call:

maximumExpeditionSize(lessExperienced = List.of(0, 1, 1, 3, 2), moreExperienced = List.of(2, 2, 1, 1, 0))

Output: 3

Explanation: Climbers 1, 2, and 4 can be selected. They respectively have 0, 1, and 2 less-experienced selected members. Their more-experienced counts are 2, 1, and 0. All their limits are satisfied, but no valid group of four climbers exists.

Example 2

Method Call:

maximumExpeditionSize(lessExperienced = List.of(0, 1, 0, 2, 2, 3, 4), moreExperienced = List.of(4, 3, 3, 2, 1, 1, 0))

Output: 5

Explanation: Climbers 1, 2, 4, 6, and 7 form a valid expedition. An expedition of six climbers is impossible because its least-experienced member would need to accept five more-experienced members.

Example 3

Method Call:

maximumExpeditionSize(lessExperienced = List.of(0, 0, 0, 0), moreExperienced = List.of(0, 0, 0, 0))

Output: 1

Explanation: Every climber is willing to join only when there are no less-experienced or more-experienced members. Therefore, only one climber can be selected.