情侣牵手
Couples Holding Hands
题目详情
问题：情侣牵手
考察：贪心、深度优先搜索、广度优先搜索
来源：DSA Prep / Citadel
链接：https://leetcode.com/problems/couples-holding-hands
英文原题
Problem: Couples Holding Hands
Patterns: Greedy, Depth-First Search, Breadth-First Search
Recency: 2yr
Link: https://leetcode.com/problems/couples-holding-hands
Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/
解析
思路：把每对情侣看作一个组，当前座位相邻两人若不是一对，就把其中一人的伴侣交换到旁边。也可建图/并查集：每个连通块大小为 m，需要 m-1 次交换。
复杂度：贪心配合位置表 O(n)，空间 O(n)。
英文解析
Approach: Model each couple as a group. Greedily fix seats in pairs by swapping the partner of the first seated person into the adjacent seat, updating positions after each swap.
Complexity: Time , space .