CSES - Restaurant Customers | Khách nhà hàng - LQDOJ: Le Quy Don Online Judge

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

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))

4 bình luận nữa