Minimum Number of Swaps to Arrange Couples

If you’re not a medium member, you can read the story through this link.

We are given 2×N seats, where N couples are sitting in random order. Our task is to rearrange them so that each couple is sitting together. A couple is identified by having two consecutive seat positions. We need to determine the minimum number of swaps required to achieve this arrangement.

Key Insights:

1. Pair Identification: Each individual has a unique identifier, but we can say that persons i and i+1 form a couple (or any unique pair). For instance, if persons are indexed from 0, then a couple could be (0,1),(2,3),…,(2×N−2,2×N−1).
2. Swaps: A swap can be considered as exchanging the positions of two people. The goal is to reduce the number of mismatched pairs in the least number of swaps.

Approach:

This problem can be mapped as a minimum swap problem in a permutation. We’ll use greedy swaps to correct the position of each person to form couples side-by-side.

Steps:

Create a mapping:
We’ll create a map that links each person to their partner. For instance, if person 0 is the partner of person 1, and 2 is the partner of person 3, this will be used to easily identify the correct couple positions.