🔗 🟢 2037. Minimum Number of Moves to Seat Everyone 1357

tags: `Biweekly Contest 63` `貪心(Greedy)` `排序(Sorting)`

題意

有 $n$ 個座位和 $n$ 個學生在一個房間裡。給定長度為 $n$ 的座位陣列 $\text{seats}$ 和同樣長度的學生陣列 $\text{students}$ ，其中 $\text{seats}[i]$ 是第 $i$ 個座位的位置、 $\text{students}[j]$ 是第 $j$ 個學生的位置。

你可以執行以下移動任意次：

增加或減少第 $i$ 個學生的位置 $1$ (即，將第 $i$ 個學生從位置 $x$ 移動到 $x + 1$ 或 $x - 1$ )

返回將每個學生移動到一個座位的最小移動次數，使得沒有兩個學生在同一個座位上。

注意：同一個位置上可能有多個座位，且初始時可能有多個學生在同一個位置。

約束條件

$n = \text{seats.length} = \text{students.length}$
$1 \leq n \leq 100$
$1 \leq \text{seats}[i], \text{students}[j] \leq 100$

思路：貪心(Greedy) + 排序(Sorting)

因為學生數和座位數相同，且每個學生都有一個座位，故每個學生都會坐在一個座位上。而為了使移動次數最小，可以基於貪心思路，讓第一個學生坐在第一個座位上，第二個學生坐在第二個座位上，以此類推，使得每個學生到其對應的座位的移動次數最小。

故可以先將學生和座位分別由小到大排序，計算每個學生到其對應座位的移動次數 $|seats[i] - students[i]|$ ，所求為 $\displaystyle\sum_{i=0}^{n-1} |seats[i] - students[i]|$ 。

此外，可以注意到約束條件中 $1 \leq \text{seats}[i], \text{students}[j] \leq 100$ ，故可以使用計數排序，時間複雜度為 $\mathcal{O}(D)$ ，其中 $D$ 為值域大小。

複雜度分析

時間複雜度： $\mathcal{O}(n\log n)$ $O (n lo g n)$ 。
- 若使用計數排序，時間複雜度為 $\mathcal{O}(D)$ ，其中 $D$ 為值域大小，此題 $D = 101$ 。
空間複雜度： $\mathcal{O}(1)$ ，忽略排序所需的空間。

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        seats.sort()
        students.sort()
        return sum(abs(x - y) for x, y in zip(seats, students))

class Solution {
public:
    int minMovesToSeat(vector<int>& seats, vector<int>& students) {
        int n = seats.size(), ans = 0;
        sort(seats.begin(), seats.end());
        sort(students.begin(), students.end());
        for (int i = 0; i < n; i++) {
            ans += abs(seats[i] - students[i]);
        }
        return ans;
    }
};