CSES - Restaurant Customers | Khách nhà hàng

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Tác giả:

Flower_On_Stone , Elektrikar

Dạng bài

Điểm: 1000 Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Bạn được cho thời gian đến và rời đi của \(n\) khách hàng trong một nhà hàng.

Số lượng khách hàng tối đa trong nhà hàng bất cứ lúc nào là bao nhiêu?

Input

Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng khách hàng.
Sau này, có \(n\) dòng mô tả khách hàng. Mỗi dòng có hai số nguyên \(a\) và \(b\): thời gian đến và rời của khách hàng.
Bạn có thể giả định rằng tất cả thời gian đến và đi là khác nhau.

Output

In một số nguyên: số lượng khách hàng tối đa.

Constraints

\(1 \le n \le 2 \cdot 10^5\)
\(1 \le a < b \le 10^9\)

Example

Sample input

Sample output

Bình luận

-1

thenomalnoob 1:41 p.m. 17 Tháng 9, 2024

Bài này sweep line

def solve(customers):
    arrival = sorted([i[0] for i in customers])
    departure = sorted([i[1] for i in customers])

    n = len(arrival)
    i = 0
    j = 0
    current_customers = 0
    max_customers = 0
    while i < n and j < n:
        if arrival[i] <= departure[j]:
            current_customers += 1
            i += 1
        else:
            j += 1
            current_customers -= 1
        max_customers = max(max_customers, current_customers)

    return max_customers

t = int(input())
l = []
for i in range(t):
    l.append([int(x) for x in input().split()])

print(solve(l))

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;

for (int i = 1; i <= n; i++) {
    long long u, v;
    cin >> u >> v;
    a.push_back({u, 1});
    a.push_back({v, -1});
}

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

int ds = 0;
int max_ds = 0;

for (int i = 0; i < a.size(); i++) {
    int m = a[i].second;
    ds += m;
    max_ds = max(max_ds, ds);
}

cout << max_ds << '\n';

return 0;

}

-2

havanxt 11:11 p.m. 17 Tháng 9, 2023

hơi khó đế

-40

Vudoanh908 7:08 p.m. 16 Tháng 11, 2022

Phi phai

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.