รถไฟสูงสุดที่สามารถหยุดน้ำได้ใน C++

ในปัญหานี้ เราได้รับจำนวน N แทนจำนวนแพลตฟอร์มของสถานีที่มีทางรถไฟสองทางต่อแพลตฟอร์มหนึ่ง และมีรถไฟ T ขบวนผ่านสถานี ซึ่งมีเวลาถึงและเวลาออกกำหนดไว้ แต่ละขบวนหยุดที่แพลตฟอร์มเฉพาะ ภารกิจคือการสร้างโปรแกรมหาจำนวนรถไฟสูงสุดที่สามารถหยุดน้ำได้ใน C++

ตัวอย่างเพื่อเข้าใจปัญหา:

อินพุต

N = 3, T = 5
Trains = {{0915, 0930, 2}, {0930, 0945, 1}, {0930, 1200, 1}, {0910, 0925, 3}, {0940, 1015, 1}}

เอาต์พุต

4

คำอธิบาย

ตารางรถไฟ:
Train 1: หยุดที่แพลตฟอร์ม 2 - 09:15-09:30
Train 2: หยุดที่แพลตฟอร์ม 1 - 09:30-09:45
Train 3: ไม่ได้หยุด
Train 4: หยุดที่แพลตฟอร์ม 3 - 09:10-09:25
Train 5: หยุดที่แพลตฟอร์ม 1 - 09:40-10:15

แนวทางแก้ปัญหา

วิธีแก้ต้องใช้ greedy approach (วิธี貪婪) เนื่องจากเราต้องหาจำนวนรถไฟสูงสุดที่สามารถหยุดได้

เราจะใช้ activity selection approach (การเลือกกิจกรรม) เพื่อหาวิธีแก้ที่เหมาะสมที่สุด สำหรับแต่ละแพลตฟอร์ม เราจะสร้าง vector เพื่อเก็บข้อมูลรถไฟ และหาวิธีแก้ที่เหมาะสมที่สุด

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

#include <bits/stdc++.h>
using namespace std;

int maxStop(int trains[][3], int N, int T) {
    vector<pair<int, int> > tStopping[N + 1];
    int trainsStopped = 0;
    
    for (int i = 0; i < T; i++)
        tStopping[trains[i][2]].push_back(make_pair(trains[i][1], trains[i][0]));
    
    for (int i = 0; i <= N; i++)
        sort(tStopping[i].begin(), tStopping[i].end());
    
    for (int i = 0; i <= N; i++) {
        if (tStopping[i].size() == 0)
            continue;
        int a = 0;
        trainsStopped++;
        for (int j = 1; j < tStopping[i].size(); j++) {
            if (tStopping[i][j].second >= tStopping[i][a].first) {
                a = j;
                trainsStopped++;
            }
        }
    }
    return trainsStopped;
}

int main() {
    int N = 3;
    int T = 5;
    int trains[T][3] = {{915, 930, 2}, {930, 945, 3}, {930, 1200, 1}, {910, 925, 3}, {940, 1015, 1}};
    cout << "The Maximum No. of Trains Stopped at the station is " << maxStop(trains, N, T);
    return 0;
}

ผลลัพธ์

The Maximum No. of Trains Stopped at the station is 4