Maximum People in Trip Group
There are n people. Each person has a minimum and maximum number of other people they need in the same group to go on a trip. Find the maximum number of people who can be arranged into valid trip groups.
For a person i, minPeople.get(i) is the minimum number of other people required in their group, and maxPeople.get(i) is the maximum number of other people allowed in their group. A person can go on the trip only if their group size excluding themselves is within this range.
People may be split into one or more groups. A person can belong to at most one group. Some people may be left out.
Class Trip Group Planner
Method
Maximum People On Trip
int maximumPeopleOnTrip(List<Integer> minPeople, List<Integer> maxPeople)
- Returns the maximum number of people who can be placed into valid groups.
- A group of size
g is valid for person i only when minPeople.get(i) ≤ g - 1 ≤ maxPeople.get(i).
- Each person can be used in at most one group.
- If multiple valid arrangements exist, only the maximum count is returned, so the output is deterministic.
Constraints
1 ≤ n ≤ 15minPeople.size() = nmaxPeople.size() = n0 ≤ minPeople.get(i) ≤ maxPeople.get(i) < n- All values are integers.
Examples
Example 1
maximumPeopleOnTrip(minPeople = [1, 1, 1, 1], maxPeople = [1, 1, 1, 1])
- Output:
4
- Explanation: All people need exactly one other person, so they can form two groups of size
2.
Example 2
maximumPeopleOnTrip(minPeople = [1, 1, 1], maxPeople = [1, 1, 1])
- Output:
2
- Explanation: Two people can form one valid group of size
2. The remaining person cannot go alone.
Example 3
maximumPeopleOnTrip(minPeople = [0, 0, 2, 2, 2], maxPeople = [0, 1, 4, 4, 4])
- Output:
4
- Explanation: One person can go alone, and three people who need at least two other people can form a group of size
3.
Example 4
maximumPeopleOnTrip(minPeople = [2, 2, 2, 2], maxPeople = [2, 2, 2, 2])
- Output:
3
- Explanation: A valid group must have exactly
3 people. One person is left out.