Good Morning
Problem
You're given a set of hotel rooms, each room has it's own priority and each room has a client.
You have to minimize the number of repeating clients in the hotel rooms, according to the rules:
- You can only swap clients with the same priority.
- You are not allowed to swap rooms.
- You are not allowed to swap priorities.
Limitations:
0 < Rooms < 1000
0 < Priority < 10^9
'A' < Client < 'Z'
Example
Input:
Output:
The following example shows:
- in the picture1 — client "B" is repeating.
- in the picture2 — there are no repeating clients.
Thoughts
- I converted it to the graph and tried DFS + Multiset, but the complexity was exponential
- Tried to create a solution using randomization, but I didn't get to it.
- I googled and didn't find similar problems.