Problem Statement
The recent pandemic forced many airlines to downsize.
Our airline is currently serving N airports, numbered from 0 to N-1. We have M bidirectional flights: flight i operates between airports A[i] and B[i].
We want to keep only a profitable subset of airports and stop servicing all others. For the purpose of this problem, the profitability of a non-empty subset S of airports is defined as f(S) / |S|, where f(S) is the number of flights with both endpoints in S, and |S| is the size of S.
Find and return any non-empty subset of airports with the maximum profitability.
Definition
- Class:
- FlightReduction
- Method:
- reduce
- Parameters:
- int, int[], int[]
- Returns:
- int[]
- Method signature:
- int[] reduce(int N, int[] A, int[] B)
- (be sure your method is public)
Notes
- All optimal answers will be accepted. The order in which you output the airports you want to keep does not matter (but you must output each only once).
Constraints
- N will be between 1 and 60, inclusive.
- A will have between 0 and 150 elements, inclusive.
- B will have the same number of elements as A.
- Each pair (A[i], B[i]) will consist of two distinct airports.
- All unordered pairs (A[i], B[i]) will be distinct.
Examples
7
{2}{5}Returns: {2, 5 }We should drop all airports from which we have no flights, and keep only airports 2 and 5.5
{0, 1, 2, 3, 0, 1, 2}{1, 2, 3, 0, 2, 3, 4}Returns: {0, 1, 2, 3 }Currently we have 7 flights and 5 airports, for a profitability of 1.4. If we drop airport 4, we will have 6 flights and 4 airports, which increased our profitability to 1.5.2
{}{}Returns: {0 }Remember that we need to keep a non-empty subset of airports.