Hoàn Thành Công Việc

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie có $N$ công việc có thể hoàn thành. Mỗi công việc $i$ có hạn bắt đầu $s_{i}$ và thời gian thực hiện $t_{i}$ . Công việc phải bắt đầu không muộn hơn thời điểm $s_{i}$ và chạy liên tục cho đến khi hoàn thành. Tìm số công việc tối đa có thể hoàn thành bắt đầu từ thời điểm $0$ .

Dữ liệu vào

Dòng đầu: $T$ ( $1 \leq T \leq 10$ ) là số test case.
Mỗi test case:
- Dòng $1$ : Số nguyên $N$ ( $1 \leq N \leq 2 \cdot 10^{5}$ ).
- $N$ dòng tiếp theo: Hai số nguyên $s_{i}$ và $t_{i}$ ( $0 \leq s_{i} \leq 10^{18}$ , $1 \leq t_{i} \leq 10^{18}$ ).
Tổng $N$ qua tất cả test case $\leq 3 \cdot 10^{5}$ .

Dữ liệu ra

Mỗi test case in ra một số nguyên - số công việc tối đa có thể hoàn thành.

Ràng buộc

Test $2$ - $3$ : Tất cả $t_{i}$ bằng nhau
Test $4$ - $5$ : $N \leq 5000$
Test $6$ - $16$ : Không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
3 2 1 4 1 2 2 2 3 1 2 3 1 4 2 3 1 2	1 2 2	Test 1: Chỉ hoàn thành được 1 trong 2 công việc. Test 2: Cả hai công việc đều hoàn thành được.

Bình luận

Không có bình luận tại thời điểm này.