2. Leetcode 765. Couples Holding Hands

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples' initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Thought:

2N seats, N couples, we treat every two adjacent seats as a node, and two nodes could be connected if there is a valid swap, a valid swap means, after swapping two people, we can make at least one couple sitting together. Nodes connected by those valid swaps, then N nodes were grouped into several components. what we want to do to is cutting edges, doing swaps, then generating N isolated nodes. One fact we need to know is each swapping, we can only generate one more isolated node. Then, if we have a connected components, and want to generate b nodes, we only need to do b - a times swapping.

Another way to solve this question is, for each invalid node, which means the people sitting in this node is not a couple. Then we have two swapping choices to make it valid. If we think deeply, those two choices have same effect, which means, no matter we choose which choice, we can reach same result.

Then this problem can be solved by Greedy.

//Solution one: Union Find 

class Solution 

{

public:

    int minSwapsCouples(vector<int>& row)

    {

        int n = row.size() / 2;

        vector<int> PersonToNode(row.size(), 0);

        for(size_t i = 0;i < row.size();i++)

        {

            PersonToNode[row[i]] = i / 2;

        }

        vector<int> parents(n, 0);

        for(int i = 0;i < n;i++)

        {

            parents[i] = i;

        }

        int components = n;

        for(size_t i = 0;i < row.size();i++)

        {

            int left  = i / 2;

            int right = (row[i] % 2 == 0 ? PersonToNode[row[i]+1] : PersonToNode(row[i] - 1));

            if(left == right)

                continue;

            while(parent[left] != left)

                left = parent[left];

            while(parent[right] != right)

                right = parent[right];

            if(left != right)

            {

                parent[left] = right;

                components--;

            }

        }

        return n - components;

    }

};

//Greedy 

class Solution {

public:

    int minSwapsCouples(vector<int>& row) {

        int n = row.size();

        vector<int> PersonToNode(n, 0);

        for(size_t i = 0;i < row.size();i++)

            PersonToNode[row[i]] = i;

        int count = 0;

        for(size_t i = 0;i < row.size();i+=2)

        {

            int left = row[i];

            int right = row[i+1];

            int target = row[i] % 2 != 0 ? row[i] - 1 : row[i] + 1;

            if(right == target) 

                continue;

            row[i+1] = target;

            PersonToNode[right] = PersonToNode[target];

            row[PersonToNode[right]] = right;

            count++;

        }

        return count;

    }

};