Vấn đề về số lượng nền tảng tối thiểu

Danh sách thời gian đến và đi được đưa ra. Bây giờ, vấn đề là phải tìm ra số lượng sân ga tối thiểu cần thiết cho đường sắt vì không có tàu nào chờ đợi.

Bằng cách sắp xếp tất cả thời gian theo thứ tự đã sắp xếp, chúng ta có thể dễ dàng tìm ra lời giải, sẽ dễ dàng theo dõi khi tàu đến nhưng chưa rời ga.

Độ phức tạp về thời gian của bài toán này là O (n Log n).

Đầu vào và Đầu ra

Input:
Lists of arrival time and departure time.
Arrival: {900, 940, 950, 1100, 1500, 1800}
Departure: {910, 1200, 1120, 1130, 1900, 2000}
Output:
Minimum Number of Platforms Required: 3

Thuật toán

minPlatform(arrival, departure, int n)

Đầu vào - Danh sách thời gian đến và thời gian khởi hành, và số lượng các mặt hàng trong danh sách

Đầu ra - Số lượng nền tảng tối thiểu là cần thiết để giải quyết vấn đề.

Begin
   sort arrival time list, and departure time list
   platform := 1 and minPlatform := 1
   i := 1 and j := 0

   for elements in arrival list ‘i’ and departure list ‘j’ do
      if arrival[i] < departure[j] then
         platform := platform + 1
         i := i+1
         if platform > minPlatform then
            minPlatform := platform
      else
         platform := platform – 1
         j := j + 1
   done
   return minPlatform
End

Ví dụ

#include<iostream>
#include<algorithm>
using namespace std;

int minPlatform(int arrival[], int departure[], int n) {
   sort(arrival, arrival+n);     //sort arrival and departure times
   sort(departure, departure+n);

   int platform = 1, minPlatform = 1;
   int i = 1, j = 0;

   while (i < n && j < n) {
      if (arrival[i] < departure[j]) {
         platform++;     //platform added
         i++;
         if (platform > minPlatform)    //if platform value is greater, update minPlatform
            minPlatform = platform;
      } else {
         platform--;      //delete platform
         j++;
      }
   }
   return minPlatform;
}

int main() {
   int arrival[] = {900, 940, 950, 1100, 1500, 1800};
   int departure[] = {910, 1200, 1120, 1130, 1900, 2000};
   int n = 6;
   cout << "Minimum Number of Platforms Required: " << minPlatform(arrival, departure, n);
}

Đầu ra

Minimum Number of Platforms Required: 3