ปัญหาจำนวนแพลตฟอร์มขั้นต่ำ

รายการเวลาที่มาถึงและออกเดินทางจะได้รับ ตอนนี้ปัญหาอยู่ที่การหาจำนวนชานชาลาขั้นต่ำที่จำเป็นสำหรับทางรถไฟเนื่องจากไม่มีรถไฟคอยรอ

โดยการเรียงลำดับเวลาทั้งหมดตามลำดับการเรียงลำดับ เราจะสามารถค้นหาวิธีแก้ปัญหาได้ง่าย มันจะง่ายต่อการติดตามเมื่อรถไฟมาถึงแต่ไม่ออกจากสถานี

ความซับซ้อนของเวลาของปัญหานี้คือ O(n Log n)

อินพุตและเอาต์พุต

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

อัลกอริทึม

minPlatform(arrival, departure, int 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

ตัวอย่าง

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

ผลลัพธ์

Minimum Number of Platforms Required: 3