Q:
There are N office buildings numbered by 0 to N-1. Each employee has a space in one of the buildings. Emloyees can make a request to relocate from building X to building Y with following format:
{"Name", fromBuilding, toBuilding }
Initially all buildings are full. Given a wishlist of requests, find an algorihm to plan the relocations by fulfilling maximum number of requests. Output will be names of requesters to relocate in a cylic path.
Example 1:
Input:
{"Alex", 1, 2 }
{"Ben", 2, 1 }
{"Chris", 1, 2 }
{"David", 2, 3 }
{"Ellen", 3, 1 }
{"Frank", 4, 5 }
Output:
["Alex","Ben"]
["Chris","David","Ellen"]
Explanation:
Alex change offices with Ben.
Chris moves to David’s place, David moves to Ellen’s and Ellen moves back to Chris’s place.
Frank doesn’t move.
Example 2:
Input:
{"Alex", 1, 2 }
{"Ben", 2, 1 }
{"Chris", 4, 5 }
{"David", 5, 1 }
{"Ellen", 2, 3 }
{"Frank", 3, 4 }
Output:
["Alex","Ellen","Frank","Chris","David"]
Explanation:
When Alex can move in place of two employees (“Ben” and “Ellen”), pick the one who forms the longer cycle (“Ellen”).
“Ben” doesn’t move.