ปัญหาจำนวนแพลตฟอร์มขั้นต่ำ (Minimum Number of Platforms Problem)

บทนำ

ปัญหานี้กำหนดรายการเวลาการมาถึง (Arrival) และเวลาการออกเดินทาง (Departure) ของรถไฟหลายขบวน วัตถุประสงค์คือการหาจำนวนแพลตฟอร์มขั้นต่ำที่จำเป็นสำหรับสถานีรถไฟ เพื่อให้รถไฟทุกขบวนไม่ต้องรอคอย

แนวคิดการแก้ปัญหา

โดยการจัดเรียง (Sort) เวลาทั้งหมดตามลำดับ จะทำให้ติดตามได้ง่ายว่าเมื่อใดมีรถไฟมาถึงแต่ยังไม่ได้ออกจากสถานี ซึ่งเป็นช่วงเวลาที่ต้องใช้แพลตฟอร์ม

ความซับซ้อนของเวลา (Time Complexity)

O(n log n) โดยที่ n คือจำนวนรถไฟ

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

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

อัลกอริทึม

minPlatform(arrival, departure, n)

Input: รายการเวลามาถึง, รายการเวลาออก, จำนวนรายการ
Output: จำนวนแพลตฟอร์มขั้นต่ำที่ต้องการ

Begin
    เรียงลำดับรายการ arrival และ departure
    platform := 1 และ minPlatform := 1
    i := 1 และ j := 0
    สำหรับแต่ละรายการใน arrival 'i' และ departure '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

ตัวอย่างโค้ด (C++)

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

int minPlatform(int arrival[], int departure[], int n) {
    sort(arrival, arrival+n);      // เรียงเวลามาถึงและออก
    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++;            // เพิ่มแพลตฟอร์ม
            i++;
            if (platform > minPlatform)
                minPlatform = platform;  // อัปเดตค่าสูงสุด
        } else {
            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