จำนวนแพลตฟอร์มขั้นต่ำที่จำเป็นสำหรับสถานีรถไฟด้วย C++

ข้อความโจทย์

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

เราได้รับสองอาร์เรย์ที่แสดงเวลาการมาถึงและเวลาออกเดินทางของรถไฟที่หยุด

สำหรับข้อมูลนำเข้าด้านล่าง เราต้องการแพลตฟอร์มอย่างน้อย 3 แห่ง -

อัลกอริทึม

1. เรียงลำดับอาร์เรย์เวลามาถึงและเวลาออกจากน้อยไปมาก
2. ติดตามจำนวนรถไฟในเวลาใดเวลาหนึ่ง โดยนับรถไฟที่มาถึงแล้วแต่ยังไม่ได้ออก

ตัวอย่างโค้ด

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

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Minimum required platforms = 3