Số lượng nền tảng tối thiểu cần thiết cho một nhà ga sử dụng C ++.

Tuyên bố vấn đề

Với thời gian đến và đi của tất cả các chuyến tàu đến một nhà ga, nhiệm vụ là tìm số lượng sân ga tối thiểu cần thiết cho nhà ga để không có chuyến tàu nào phải chờ đợi.

Chúng tôi được cung cấp hai mảng đại diện cho thời gian đến và đi của các chuyến tàu dừng lại.

Đối với đầu vào dưới đây, chúng tôi cần ít nhất 3 nền tảng -

Thuật toán

1. Sort arrival and departure time arrays in ascending order
2. Trace the number of trains at any time keeping track of trains that haves arrived, but not departed

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;
}

Đầu ra

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