Đề bài
Cho thời gian đến và đi của tất cả các tàu đến một ga tàu hỏa, nhiệm vụ là tìm số lượng sân ga tối thiểu cần thiết cho ga tàu hỏa để không có tàu nào phải chờ đợi.
Chúng ta được cho hai mảng đại diện cho thời gian đến và đi của các tàu dừng lại.
Đối với đầu vào dưới đây, chúng ta cần ít nhất 3 sân ga:
| Tàu | Thời gian đến | Thời gian đi |
|---|---|---|
| Tàu-1 | 09:00 | 09:15 |
| Tàu-2 | 09:35 | 11:45 |
| Tàu-3 | 09:40 | 11:05 |
| Tàu-4 | 11:00 | 12:00 |
| Tàu-5 | 14:30 | 18:15 |
| Tàu-6 | 18:00 | 19:00 |
Thuật toán
1. Sắp xếp mảng thời gian đến và đi theo thứ tự tăng dần 2. Theo dõi số lượng tàu tại bất kỳ thời điểm nào, giữ trace của các tàu đã đến nhưng chưa đi
Ví dụ
#include <iostream> #include <algorithm> #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) using namespace std; int getPlatformCount(int *arrival, int *departure, int n){ sort(arrival, arrival + n); sort(departure, departure + n); int platformCnt = 1; int result = 1; int i = 1; int j = 0; while (i < n && j < n) { if (arrival[i] <= departure[j]) { ++platformCnt; ++i; if (platformCnt > result) { result = platformCnt; } } else { --platformCnt; ++j; } } return result; } int main() { int arrival[] = {900, 935, 940, 1100, 1430, 1800}; int departure[] = {915, 1145, 1105, 1200, 1815, 1900}; cout << "Minimum required platforms = " << getPlatformCount(arrival, departure, SIZE(arrival)) << endl; return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Minimum required platforms = 3