Minimum Number of Moves to Seat Everyone (LeetCode 2037)

Nguồn: LeetCode 2037 Độ khó: Dễ Tham lam Sắp xếp

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

2037. Minimum Number of Moves to Seat Everyone – Số bước di chuyển ít nhất để xếp chỗ cho mọi người (LeetCode, độ khó Easy)

Trong một căn phòng có $n$ chỗ ngồi và $n$ học sinh. Cho mảng seats độ dài $n$, trong đó seats[i] là vị trí của chỗ ngồi thứ $i$. Cho thêm mảng students độ dài $n$, trong đó students[j] là vị trí của học sinh thứ $j$.

Bạn có thể thực hiện thao tác sau bao nhiêu lần tùy ý:

• Tăng hoặc giảm vị trí của học sinh thứ $i$ đi $1$ (tức là di chuyển học sinh thứ $i$ từ vị trí $x$ sang $x + 1$ hoặc $x - 1$).

Hãy trả về số bước di chuyển ít nhất để đưa mỗi học sinh về một chỗ ngồi sao cho không có hai học sinh nào ngồi cùng một chỗ.

Lưu ý rằng lúc đầu có thể có nhiều chỗ ngồi hoặc nhiều học sinh ở cùng một vị trí.

Ràng buộc:

• $n$ == seats.length == students.length
• $1 \le n \le 100$
• $1 \le$ seats[i], students[j] $\le 100$

Định dạng vào/ra để chạy thử trên máy: trên LeetCode các bạn chỉ cần viết hàm minMovesToSeat trong class Solution. Để chạy được như một chương trình bình thường (và dùng được khung chạy tay bên dưới), mình đặt thêm định dạng:

• Dữ liệu vào: dòng đầu là số nguyên $n$; dòng thứ hai gồm $n$ số seats[0..n-1]; dòng thứ ba gồm $n$ số students[0..n-1].
• Kết quả: một số nguyên là số bước di chuyển ít nhất.

2037. Minimum Number of Moves to Seat Everyone (LeetCode, Easy)

There are n seats and n students in a room. You are given an array seats of length n, where seats[i] is the position of the ith seat. You are also given the array students of length n, where students[j] is the position of the jth student.

You may perform the following move any number of times:

• Increase or decrease the position of the ith student by 1 (i.e., moving the ith student from position x to x + 1 or x - 1)

Return the minimum number of moves required to move each student to a seat such that no two students are in the same seat.

Note that there may be multiple seats or students in the same position at the beginning.

Example 1: Input: seats = [3,1,5], students = [2,7,4] – Output: 4
Explanation: The students are moved as follows:
- The first student is moved from position 2 to position 1 using 1 move.
- The second student is moved from position 7 to position 5 using 2 moves.
- The third student is moved from position 4 to position 3 using 1 move.
In total, 1 + 2 + 1 = 4 moves were used.

Example 2: Input: seats = [4,1,5,9], students = [1,3,2,6] – Output: 7
Explanation: The students are moved as follows:
- The first student is not moved.
- The second student is moved from position 3 to position 4 using 1 move.
- The third student is moved from position 2 to position 5 using 3 moves.
- The fourth student is moved from position 6 to position 9 using 3 moves.
In total, 0 + 1 + 3 + 3 = 7 moves were used.

Constraints:

• n == seats.length == students.length
• 1 <= n <= 100
• 1 <= seats[i], students[j] <= 100

Ví dụ 1 – LeetCode

Input: seats = [3,1,5], students = [2,7,4]
Output: 4

Ví dụ 1 – stdin / stdout

3
3 1 5
2 7 4
---
4

Ví dụ 2 – LeetCode

Input: seats = [4,1,5,9], students = [1,3,2,6]
Output: 7

Ví dụ 2 – stdin / stdout

4
4 1 5 9
1 3 2 6
---
7

Giải thích ví dụ của đề:

• Ví dụ 1: học sinh thứ nhất đi từ vị trí 2 tới vị trí 1 mất 1 bước; học sinh thứ hai đi từ 7 tới 5 mất 2 bước; học sinh thứ ba đi từ 4 tới 3 mất 1 bước. Tổng cộng $1 + 2 + 1 = 4$ bước.
• Ví dụ 2: học sinh thứ nhất không cần di chuyển (đang ở vị trí 1, đúng chỗ ngồi 1); học sinh thứ hai đi từ 3 tới 4 mất 1 bước; học sinh thứ ba đi từ 2 tới 5 mất 3 bước; học sinh thứ tư đi từ 6 tới 9 mất 3 bước. Tổng cộng $0 + 1 + 3 + 3 = 7$ bước.

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Lưu ý nhỏ: khi nộp trên CLUE OJ các bạn dán toàn bộ code, gồm cả hàm main, vì đề trên CLUE OJ đọc dữ liệu vào và in kết quả đúng theo định dạng ở phần đề bài, giống như khi các bạn chạy thử trên máy hoặc ở trang Chạy code online của blog.

Tóm tắt đề bài: có $N$ học sinh, học sinh thứ $i$ hiện đang ở vị trí students[i]. Có $N$ chỗ ngồi, chỗ ngồi thứ $i$ ở vị trí seats[i]. Ta cần sắp xếp $N$ học sinh vào $N$ chỗ ngồi sao cho mỗi học sinh ngồi đúng 1 chỗ, và tổng số bước di chuyển là ít nhất có thể. Học sinh ở vị trí $x$ mỗi bước có thể tiến thêm 1 hoặc lùi 1, tức là đi tới $x + 1$ hoặc $x - 1$. Như vậy học sinh ở vị trí $x$ đi tới chỗ ngồi ở vị trí $y$ mất đúng $|x - y|$ bước.

Ở ví dụ 1, nếu nhìn trên trục số: các chỗ ngồi ở $1, 3, 5$, các học sinh ở $2, 4, 7$. Học sinh trái nhất (ở 2) ngồi chỗ trái nhất (ở 1), học sinh giữa (ở 4) ngồi chỗ giữa (ở 3), học sinh phải nhất (ở 7) ngồi chỗ phải nhất (ở 5) – đó chính là cách xếp của đề, và cũng là ý tưởng của lời giải bên dưới.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Sắp xếp + tham lam · O(N log N)

Cách 1Sắp xếp rồi ghép theo thứ tự – O(N log N)

Phương pháp giải: Tham lam. Để bảo đảm số lượng bước di chuyển là tối thiểu, ta chỉ cần xếp học sinh "gần đầu" nhất vào chỗ ngồi "gần đầu" nhất, học sinh gần nhì vào chỗ ngồi gần nhì, ... cứ thế tới hết.

Ý tưởng chính

Sắp xếp tăng dần vị trí các chỗ ngồi và vị trí các học sinh. Sau khi sắp xếp, học sinh thứ $i$ ngồi vào chỗ ngồi thứ $i$, tốn $|students[i] - seats[i]|$ bước. Đáp án là $|students[0] - seats[0]| + |students[1] - seats[1]| + \dots + |students[N-1] - seats[N-1]|$.

Vì sao ghép theo thứ tự lại tối ưu? Giả sử trong một cách xếp nào đó có hai học sinh ở $x_1 \le x_2$ nhưng lại ngồi "chéo nhau": học sinh $x_1$ ngồi chỗ $y_2$, học sinh $x_2$ ngồi chỗ $y_1$ với $y_1 \le y_2$. Khi đổi chỗ cho hai bạn này (để $x_1 \to y_1$, $x_2 \to y_2$) thì tổng số bước không tăng:

Bất đẳng thức đổi chỗ

$|x_1 - y_1| + |x_2 - y_2| \le |x_1 - y_2| + |x_2 - y_1|$ với mọi $x_1 \le x_2$, $y_1 \le y_2$.

Các bạn có thể tự kiểm tra bằng cách xét vài trường hợp vị trí tương đối của 4 điểm trên trục số (vẽ ra là thấy ngay: hai đoạn "chéo nhau" luôn phủ ít nhất phần mà hai đoạn "song song" phủ). Cứ gỡ từng cặp chéo nhau như vậy, cuối cùng ta được cách ghép theo thứ tự mà tổng số bước không lớn hơn ban đầu, nên ghép theo thứ tự là tối ưu.

Minh hoạ trên trục số

Em nhập hai mảng (vị trí từ 1 tới 30, tối đa 8 phần tử) rồi bấm Tiếp. Hình vuông xanh dương là chỗ ngồi, hình tròn cam là học sinh. Bước đầu là cách ghép theo chỉ số ban đầu (thường bị chéo nhau, tô đỏ), sau đó sắp xếp và ghép lần lượt từng cặp:

seats students

Ví dụ nhanh:

Học sinh không cần biết mình ngồi chỗ nào lúc đầu

Đề chỉ hỏi tổng số bước, nên sắp xếp làm "mất" chỉ số ban đầu cũng không sao. Các vị trí trùng nhau (nhiều chỗ ngồi hoặc nhiều học sinh cùng một vị trí) cũng không ảnh hưởng gì: sau khi sắp xếp chúng nằm cạnh nhau và được ghép lần lượt như bình thường.

Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé. Trong hàm, mảng a là seats, mảng b là students:

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    int n;
    cin >> n;
    vector<int> seats(n), students(n);
    for (int i = 0; i < n; i++) cin >> seats[i];
    for (int i = 0; i < n; i++) cin >> students[i];
    Solution sol;
    cout << sol.minMovesToSeat(seats, students);
    return 0;
}

import sys
from typing import List

class Solution:
    def minMovesToSeat(self, a: List[int], b: List[int]) -> int:
        a.sort()
        b.sort()
        ans = 0
        for i in range(len(a)):
            ans += abs(b[i] - a[i])
        return ans

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    seats = list(map(int, data[1:1 + n]))
    students = list(map(int, data[1 + n:1 + 2 * n]))
    print(Solution().minMovesToSeat(seats, students))

if __name__ == "__main__":
    main()

Khung chạy tay bên dưới chạy đúng từng dòng của code C++ ở trên (cả hàm main lẫn hàm trong class Solution):

C++▶ Chạy tay từng dòng codeSắp xếp hai mảng tăng dần, cộng |b[i] - a[i]|, O(N log N).

Dữ liệu vào (stdin) – sửa thoải mái3 3 1 5 2 7 4

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4class Solution {

5public:

6 int minMovesToSeat(vector<int>& a, vector<int>& b) {

7 sort(a.begin(), a.end());

8 sort(b.begin(), b.end());

9 int ans = 0;

10 for (int i = 0; i < (int) a.size(); i++) {

11 ans += abs(b[i] - a[i]);

12 }

13 return ans;

14 }

15};

16

17int main() {

18 int n;

19 cin >> n;

20 vector<int> seats(n), students(n);

21 for (int i = 0; i < n; i++) cin >> seats[i];

22 for (int i = 0; i < n; i++) cin >> students[i];

23 Solution sol;

24 cout << sol.minMovesToSeat(seats, students);

25 return 0;

26}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ dùng hai mảng đầu vào và vài biến nên là $O(N)$ (bộ nhớ thêm ngoài dữ liệu vào gần như $O(1)$).
• Thời gian: hai lần sắp xếp mất $O(N \log N)$, vòng lặp cộng dồn mất $O(N)$, tổng cộng $O(N \log N)$.

Không gian$O(N)$

Thời gian$O(N \log N)$

Muốn nhanh hơn nữa?

Vì vị trí chỉ từ 1 tới 100, các bạn có thể thay sort bằng đếm phân phối để được $O(N + 100)$. Tuy nhiên với $n \le 100$ thì sắp xếp là quá đủ, code lại ngắn gọn dễ hiểu.

Ghi chú của mình: code C++ và Python đều cho đúng 2 ví dụ của đề (và thêm test seats = [2,2,6,6], students = [1,3,2,6] ra 4), và đã được so với code vét cạn thử mọi hoán vị cách ghép trên 400 bộ test ngẫu nhiên với $n \le 7$ – khớp hết. Với $n = 100$ cả hai bản đều chạy tức thì.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇