PTIT042 - Phòng thí nghiệm

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Có ~N~ lớp cần phải làm bài thực hành thí nghiệm. Mỗi lớp sẽ có thời gian bắt đầu thực hành và kết thúc. Tính số phòng thí nghiệm ít nhất cần có để tất cả ~N~ lớp đều được làm bài thực hành.

Input

  • Dòng đầu tiên chứa số nguyên dương ~N~ (~0 \le N \le 10^5~).
  • N dòng tiếp theo, mỗi dòng chưa 4 số nguyên ~G_1, P_1, G_2 ,P_2~, cho biết có lớp thực hành bắt đầu lúc ~G_1~ giờ ~P_1~ phút (~G_1:P_1~) và kết thúc vào lúc ~G_2~ giờ ~P_2~ phút (~G_2:P_2~). (~0 \le G_1, G_2 < 24~, ~0 \le P_1, P_2 < 60~).
  • Input đảm bảo thời gian bắt đầu luôn không ở sau thời gian kết thúc, hay nói cách khác, ~G_1 < G_2~ hoặc (~G_1 = G_2~ và ~P_1 \le P_2~).

Output

In ra số phòng thí nghiệm ít nhất cần thiết để tất cả các lớp đều được thực hành.

Sample

Input #1
6
1 0 5 0
17 30 20 30
6 15 15 0
20 30 22 0
20 30 22 0
12 0 13 30
Output #1
3
Input #2
2
8 10 8 13
8 13 8 15
Output #2
2

Hint

Giải thích test 1:

  1. 01:00 -- 05:00: lớp thứ nhất thực hành tại phòng số 1
  2. 17:30 -- 20:30: lớp thứ 2 thực hành tại phòng số 1 vì lúc đó phòng số 1 không có lớp nào
  3. 06:15 -- 15:00: lớp thứ 3 thực hành tại phòng số 1 vì khi đó phòng số 1 không có lớp nào
  4. 20:30 -- 22:00: lớp thứ 4 thực hành tại phòng số 2 vì khi đó phòng số 1 có lớp thứ 2 đangthực hành
  5. 20:30 -- 22:00: lớp thứ 5 thực hành tại phòng số 3 vì khi đó phòng số 1 và số 2 đang có lớp học
  6. 12:00 -- 13:30: lớp thứ 6 thực hành tại phòng số 2 vì khi đó phòng số 1 đang có lớp học.

Với test 2, lớp đầu tiên sẽ thực hành từ 08:10 đến 08:13. 08:13 là phút cuối cùng của lớp này. Do đó, để tránh xung đột thì lớp thứ hai (từ 08:13 đến 08:15) sẽ phải có một phòng khác để thực hành.

Problem source: CLB Lập Trình PTIT


Bình luận

Hãy đọc nội quy trước khi bình luận.


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