Restaurant Customers (CSES 1619)

Nguồn: CSES Problem Set – 1619 Độ khó: Trung bình Sắp xếp Sweep line Tư duy

Đề bài

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

CSES 1619 – Restaurant Customers (Khách hàng của nhà hàng)

Cho thời điểm đến và thời điểm rời đi của $n$ khách hàng trong một nhà hàng.

Hỏi số lượng khách hàng nhiều nhất có mặt trong nhà hàng tại cùng một thời điểm là bao nhiêu?

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên $n$: số lượng khách hàng.
• Tiếp theo là $n$ dòng mô tả các khách hàng. Mỗi dòng gồm hai số nguyên $a$ và $b$: thời điểm đến và thời điểm rời đi của một khách hàng.

Bạn có thể giả sử rằng tất cả các thời điểm đến và rời đi đều phân biệt (không có hai thời điểm nào trùng nhau).

Kết quả: In ra một số nguyên: số lượng khách hàng nhiều nhất.

Ràng buộc:

• $1 \le n \le 2 \cdot 10^5$
• $1 \le a \lt b \le 10^9$

Giới hạn: thời gian 1 giây, bộ nhớ 512 MB.

CSES 1619 – Restaurant Customers

Time limit: 1.00 s. Memory limit: 512 MB.

You are given the arrival and leaving times of $n$ customers in a restaurant.

What was the maximum number of customers in the restaurant at any time?

Input:

The first input line has an integer $n$: the number of customers.

After this, there are $n$ lines that describe the customers. Each line has two integers $a$ and $b$: the arrival and leaving times of a customer.

You may assume that all arrival and leaving times are distinct.

Output: Print one integer: the maximum number of customers.

Constraints:

• $1 \le n \le 2 \cdot 10^5$
• $1 \le a \lt b \le 10^9$

Ví dụ – input

3
5 8
2 4
3 9

Ví dụ – output

2

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 😇.

Nhắc lại ngưỡng TLE

Với các hệ thống chấm giới hạn 1 giây, tối đa toàn bài chỉ nên lặp khoảng $(3 \div 5) \cdot 10^7$ lần là an toàn, tệ nhất là $10^8$ (lúc này thì hên xui nhé). Ngưỡng này là cho C/C++; Python, C#, Java chạy chậm hơn nên ngưỡng phải thấp hơn. Bài này giới hạn 1 giây.

Đề gốc là tiếng Anh nhưng ngắn gọn, ở trên mình đã dịch sang tiếng Việt. Mình giải thích lại cho bạn nào chưa hiểu: ta có thời điểm đến và đi của $N$ khách hàng. Hãy tính xem tại thời điểm đông nhất, nhà hàng có bao nhiêu khách? Input dòng đầu là $N$, $N$ dòng tiếp theo mỗi dòng có 2 số $A$, $B$: $A$ là thời điểm đến, $B$ là thời điểm đi của từng khách. Output là 1 số nguyên duy nhất: số khách nhiều nhất tại 1 thời điểm.

Thời điểm lên tới 10^9

$A$, $B$ nằm trong khoảng từ 1 đến $10^9$ chứ không phải trong phạm vi 24 giờ đâu nha các bạn. Cứ hiểu thời điểm đang tính theo một đơn vị nào đó khác, nano giây chẳng hạn; tóm lại bỏ qua tính thực tế ngoài đời, chấp nhận thời điểm có thể từ 1 đến tối đa 1 tỷ.

Với ví dụ của đề: có $N = 3$ khách. Khách 1 vào lúc 5, ra lúc 8. Khách 2 vào lúc 2, ra lúc 4. Khách 3 vào lúc 3, ra lúc 9. Đáp án là 2: ví dụ tại thời điểm 6 thì khách 1 và khách 3 đều đang ở trong nhà hàng; còn không lúc nào có mặt đủ cả 3 khách (khách 2 đã về lúc 4 trước khi khách 1 tới lúc 5).

Khi nhìn vào bài có giới hạn $N$ tối đa $2 \cdot 10^5$ thì nhẩm tính được ngay: muốn chạy trong 1 giây thì toàn bài phải có độ phức tạp $O(N \log N)$ trở xuống. Nếu $O(N^2)$ thì $N^2 = 4 \cdot 10^{10}$, quá giới hạn $10^8$ ⇒ chắc chắn TLE. Còn $N \log N \approx 18 \cdot 2 \cdot 10^5 = 3{,}6 \cdot 10^6$, ít hơn ngưỡng nên yên tâm. Nhìn vào giới hạn độ lớn mà ước tính độ phức tạp cần có, từ đó định hình cách giải quyết, đó là thói quen tốt các bạn nên tập.

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ự kiện +1/−1 với vector<pair> · O(N·logN)Cách 2Cùng ý tưởng, dùng mảng tĩnh + struct + cmp

Cách 1Đếm khách theo sự kiện vào/ra – O(N·logN)

Bài này thực ra rất đơn giản nhưng mình nghĩ sẽ có nhiều bạn gặp khó khăn trong việc tìm ra cách giải quyết. Nhiều bạn sẽ nghĩ đến hướng vẽ trục số, vẽ từng đoạn thẳng $[A, B]$ trên trục số đó rồi đếm xem tại vị trí nào số đoạn chồng lên nhau nhiều nhất. Hướng như vậy tất nhiên vẫn đúng, nhưng đánh đổi lại là rất khó hình dung ra cách làm cũng như cài đặt (trục số dài tới $10^9$ thì không thể duyệt từng điểm được).

Thực ra bài này đơn giản như sau thôi các bạn:

• Ban đầu trong nhà hàng có 0 khách.
• Tại thời điểm $A$ có khách bước vào ⇒ số khách cộng thêm 1.
• Tại thời điểm $B$ khách đó bước ra ⇒ số khách giảm đi 1.

Vậy ta thống kê các cặp {A, 1} và {B, -1} (mỗi khách cho 2 cặp). Dùng cấu trúc pair với first là thời điểm, second là giá trị $1$ / $-1$. Rồi sắp xếp các cặp tăng dần theo thời điểm, khởi tạo cnt = 0 (số khách trong nhà hàng hiện tại) và duyệt lần lượt: mỗi cặp thì cnt += a[i].second (là $1$ thì tăng, là $-1$ thì giảm). Mỗi lần cập nhật cnt thì so với Max để Max luôn lưu giá trị cnt lớn nhất. Cuối cùng in Max. Bài này giải quyết đơn giản như vậy thôi đó các bạn à ^^

Ý chính

Số khách chỉ thay đổi tại các thời điểm có người vào hoặc ra. Nên thay vì xét mọi thời điểm từ 1 đến $10^9$, ta chỉ cần xét $2N$ "sự kiện" theo thứ tự thời gian, đi tới đâu cộng/trừ tới đó. Đây chính là ý tưởng đường quét (sweep line).

Bảng sự kiện với ví dụ của đề sau khi sắp xếp:

Thời điểm	Sự kiện	second	cnt	Max
2	khách 2 vào	+1	1	1
3	khách 3 vào	+1	2	2
4	khách 2 ra	−1	1	2
5	khách 1 vào	+1	2	2
8	khách 1 ra	−1	1	2
9	khách 3 ra	−1	0	2

Em nhập danh sách khách (mỗi khách 2 số: đến, đi) rồi bấm Tiếp để xem đường quét đi qua từng sự kiện:

Các cặp (đến đi)

Ví dụ nhanh:

Source code để các bạn tham khảo với hướng làm mình trình bày ở trên:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<pair<int, int>> a(2 * n);
    for(int i = 0; i < (int)a.size(); ++i){
        cin >> a[i].first;
        if(i % 2 == 0){
            a[i].second = 1;
        }
        else{
            a[i].second = -1;
        }
    }
    sort(a.begin(), a.end());
    int cnt = 0, Max = 0;
    for(int i = 0; i < (int)a.size(); ++i){
        cnt += a[i].second;
        Max = max(Max, cnt);
    }
    cout << Max;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    times = list(map(int, data[1:2 * n + 1]))
    # Gói cặp (thời điểm, đến/đi) vào 1 số nguyên cho sort nhanh:
    # e = thời điểm * 2 + 1 nếu khách đến (+1), thời điểm * 2 nếu khách đi (-1)
    a = [t * 2 + 1 for t in times[0::2]] + [t * 2 for t in times[1::2]]
    a.sort()
    cnt = 0
    Max = 0
    for e in a:
        if e & 1:
            cnt += 1
            if cnt > Max:
                Max = cnt
        else:
            cnt -= 1
    print(Max)

main()

Giải thích một số chỗ trong code ở trên:

1. 3 dòng đầu hàm main (ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);) giúp đẩy nhanh tốc độ nhập xuất với C++. Bài này input có thể lên đến $4 \cdot 10^5$ số cần nhập, là số lượng lớn, nên thêm 3 dòng này vào cho chương trình chạy nhanh hơn (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là ra rất nhiều bài giải thích nhé).
2. pair là cấu trúc có sẵn 2 thành phần first, second, rất tiện thay vì phải tự tạo struct. Và vector là mảng động có sẵn cho tiện.
3. Mỗi khách có 2 thời điểm vào và ra nên $N$ khách có $2N$ thời điểm ⇒ vector có $2N$ phần tử. Ví dụ $N = 3$ thì vector chứa: {A1, 1}, {B1, -1}, {A2, 1}, {B2, -1}, {A3, 1}, {B3, -1} ở các index $0..5$. Nên ta cho vòng lặp chạy từ 0 đến $< 2N$ (gọi nhanh bằng a.size()), mỗi lần đọc input vào a[i].first; còn a[i].second là dữ liệu ta tự tạo ra chứ không có trong input: index chẵn là $1$ (thời điểm đến), index lẻ là $-1$ (thời điểm đi).
4. sort(a.begin(), a.end()); sắp xếp vector tăng dần; với phần tử kiểu pair thì nó so sánh theo first trước. Hàm sort đảm bảo $O(N \log N)$; nếu tự cài Selection Sort, Interchange Sort, Bubble Sort… $O(N^2)$ thì sẽ bị TLE như mình phân tích ở đầu. Không dùng bits/stdc++.h thì nhớ #include <algorithm>.
5. Sau khi sắp xếp thì duyệt lại danh sách, cnt += a[i].second rồi Max = max(Max, cnt), cuối cùng in Max.
6. Bản Python: sắp xếp list các tuple khá chậm, với $N = 2 \cdot 10^5$ dễ sát 1 giây. Nên mình "gói" mỗi cặp vào 1 số nguyên: khách đến lúc $t$ thì thêm số $2t + 1$, khách đi lúc $t$ thì thêm số $2t$. Sắp xếp các số này cũng chính là sắp theo thời điểm $t$, và số lẻ nghĩa là $+1$, số chẵn nghĩa là $-1$. Ý tưởng vẫn y hệt bản C++.

C++▶ Chạy tay từng dòng codeTạo 2N cặp {thời điểm, ±1}, sắp xếp rồi cộng dồn cnt, lấy Max.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 cout.tie(0);

8 int n;

9 cin >> n;

10 vector<pair<int, int>> a(2 * n);

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

12 cin >> a[i].first;

13 if(i % 2 == 0){

14 a[i].second = 1;

15 }

16 else{

17 a[i].second = -1;

18 }

19 }

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

21 int cnt = 0, Max = 0;

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

23 cnt += a[i].second;

24 Max = max(Max, cnt);

25 }

26 cout << Max;

27 return 0;

28}

ChậmVừaNhanhRất nhanh

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

• Không gian: vector có $2N$ phần tử pair ⇒ $O(2N)$, tổng quát là $O(N)$ (theo quy tắc nhân BigO, bỏ hằng số).
• Thời gian: $O(2N)$ đọc dữ liệu + $O(N \log N)$ sắp xếp + $O(2N)$ duyệt tính kết quả. Theo quy tắc cộng BigO lấy thành phần lớn nhất ⇒ $O(N \log N)$, yên tâm không bị TLE như đã phân tích ở đầu bài.

Không gian$O(N)$

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

Nếu thời điểm có thể trùng nhau?

Đề đảm bảo mọi thời điểm đều khác nhau nên thứ tự giữa các sự kiện không bao giờ bị "hoà". Giả sử có bài biến thể cho phép một khách ra đúng lúc một khách khác vào (và coi như họ không gặp nhau) thì phải xử lý sự kiện ra ($-1$) trước sự kiện vào ($+1$) tại cùng thời điểm. Hay ở chỗ: sort trên pair khi first bằng nhau sẽ so tiếp second, mà $-1 < 1$ nên đã tự đúng luôn rồi.

Cách 2Cùng ý tưởng, dùng mảng tĩnh + struct + hàm cmp

Cũng nói thêm là bài này nếu không dùng vector và pair mà chỉ dùng mảng thường thì ta phải khai báo thêm struct Data có 2 thành phần và xây dựng hàm bool chỉ định so sánh giữa 2 cấu trúc Data là theo thành phần nào. Thuật toán y hệt cách 1 nên mình không làm khung chạy tay riêng nữa, các bạn tham khảo code nếu làm theo hướng này:

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

struct Data{
    int first, second;
};

bool cmp(const Data &a, const Data &b){
    return a.first < b.first;
}

Data a[400000];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    n *= 2;
    for(int i = 0; i < n; ++i){
        cin >> a[i].first;
        if(i % 2 == 0){
            a[i].second = 1;
        }
        else{
            a[i].second = -1;
        }
    }
    sort(a, a + n, cmp);
    int cnt = 0, Max = 0;
    for(int i = 0; i < n; ++i){
        cnt += a[i].second;
        Max = max(Max, cnt);
    }
    cout << Max;
    return 0;
}

import sys

class Data:
    __slots__ = ('first', 'second')
    def __init__(self, first, second):
        self.first = first
        self.second = second

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]) * 2
    a = [None] * n
    for i in range(n):
        a[i] = Data(int(data[1 + i]), 1 if i % 2 == 0 else -1)
    a.sort(key=lambda d: d.first)     # đóng vai trò hàm cmp
    cnt = 0
    Max = 0
    for d in a:
        cnt += d.second
        if cnt > Max:
            Max = cnt
    print(Max)

main()

Giải thích một số chỗ trong code ở trên:

1. Hàm cmp: return a.first < b.first; là viết gọn của if(a.first < b.first) return true; return false;, nghĩa là nếu first của A nhỏ hơn first của B thì là true, tức là chúng đã đứng đúng chỗ ⇒ danh sách sẽ tăng dần theo first. Nếu sai (tức first của A $\ge$ first của B) thì hàm sort sẽ đổi chỗ 2 tụi nó để về lại đúng, các bạn có thể hiểu theo ý như vậy cho dễ nhớ.
2. Mảng Data a[400000] khai báo toàn cục bên trên hàm main chứ mình không dám khai báo Data a[n]; bên trong main: $N$ tối đa $2 \cdot 10^5$ khách, nhân 2 lên là tối đa $4 \cdot 10^5$ phần tử. Theo kinh nghiệm của mình, mảng tĩnh vượt quá khoảng $3 \cdot 10^5$ phần tử thì không nên khai báo trong hàm vì bộ nhớ stack có thể không chứa nổi. Lúc này hoặc đem mảng ra ngoài làm biến toàn cục (không dùng vùng nhớ stack nên chứa được lớn hơn – cái này thuộc về kỹ thuật lập trình, bạn nào muốn thì chủ động tìm hiểu nhé), hoặc cấp phát động bằng con trỏ Data *a = new Data[n];, hoặc dùng luôn vector như cách 1.
3. sort(a, a + n, cmp); sắp xếp mảng a từ đầu mảng, đủ $n$ phần tử, theo cơ chế so sánh chỉ định bởi hàm cmp (tăng dần theo first).
4. Bản Python làm tương tự với class Data và key=lambda d: d.first đóng vai trò hàm cmp. Bản này chạy chậm hơn bản Python ở cách 1 (khoảng 0,8–0,9 giây với test lớn nhất trên máy mình) nên nếu nộp Python thì các bạn nên dùng bản cách 1.

Không gian$O(N)$

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

Ghi chú của mình: code C++ và Python của cả 2 cách đều cho đúng output ví dụ của đề, và đã được so với một chương trình vét cạn (xét từng thời điểm, đếm số khách đang có mặt) trên 400 bộ test ngẫu nhiên – khớp hết. Với test lớn nhất ($N = 2 \cdot 10^5$, thời điểm tới $10^9$) trên máy mình: C++ cách 1 khoảng 0.18 giây, cách 2 khoảng 0.11 giây; Python cách 1 khoảng 0.5–0.6 giây, cách 2 khoảng 0.8–0.9 giây.

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 😇