ในปัญหานี้ เราได้รับหมายเลข N ซึ่งแสดงถึงจำนวนชานชาลาที่สถานีหนึ่งมีโดยแต่ละแทร็กมี 2 แทร็ก และรถไฟ T จะผ่านสถานีที่มีเวลามาถึงและออก รถไฟแต่ละขบวนจะจอดที่สถานีเฉพาะ งานของเราคือสร้างโปรแกรมเพื่อค้นหารถไฟสูงสุดที่สามารถให้หยุดได้ใน C++
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
N = 3, T = 5
Trains = {{0915, 0930, 2}, {0930, 0945, 1}, {0930, 1200, 1}, {0910, 0925, 3}, {0940, 1015, 1}} ผลลัพธ์
4
คำอธิบาย
The train schedules are, Train 1: Train will be stopped at platform 2 - 09:15-09:30 Train 2: Train will be stopped at platform 1 - 09:30-09:45 Train 3: Train will be not be stopped Train 4: Train will be stopped at platform 3 - 09:10-09:25 Train 5: Train will be stopped at platform 1 - 09:40-10:15
แนวทางการแก้ปัญหา
การแก้ปัญหาต้องใช้วิธีการที่โลภเพื่อนำมาประยุกต์ใช้ เนื่องจากเราจำเป็นต้องหาจำนวนรถไฟสูงสุดที่สามารถหยุดที่สถานีได้
เราจะใช้วิธีการเลือกกิจกรรมเพื่อค้นหาวิธีแก้ไขปัญหาที่เหมาะสมที่สุด ดังนั้น สำหรับแต่ละแพลตฟอร์ม เราจะสร้างเวกเตอร์เพื่อเก็บข้อมูลของรถไฟ แล้วหาทางออกที่เหมาะสมที่สุด
ตัวอย่าง
โปรแกรมแสดงการทำงานของปัญหา
#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
