Seat the Pairs Together
An even number of people sit in a row of seats, and row[i] is the person in seat i. The people are numbered from 0, and they came in pairs: 0 with 1, 2 with 3, 4 with 5 and so on.
The seats are double seats: seats 0 and 1 belong together, then seats 2 and 3, and so on. One swap lets any two people trade places.
Return the fewest swaps after which every pair shares a double seat.
Example 1
Person 3 sits with 0. Trading 0 and 2 puts 3 next to 2, and 1 next to 0.
Example 2
Both pairs already share a double seat. The order inside a seat does not matter.
Example 3
Each double seat holds people from two different pairs, and the three pairs form one ring. The first swap completes one pair, the second completes the other two.
Constraints
2 <= len(row) <= 60, and the length is evenrowholds every number from 0 tolen(row) - 1exactly once
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Greedy problems
- Two From Every IntervalHard
- Coins Handed BackBeginner
- Coins on the TableBeginner
- Fewest BanknotesBeginner
- Fewest JugsBeginner
- Greedy CoinsBeginner
- Least Total Waiting TimeBeginner
- Most Tasks in a Time BudgetBeginner