Số tàu tối đa có thể dừng tại trạm trong C++

Cho N là số bến Bahn (mỗi bến 2 ray). T tàu qua trạm với giờ đến/đi, mỗi tàu dừng tại bến cụ thể. Tìm số tàu tối đa có thể dừng.

Ví dụ

Đầu vào: N = 3, T = 5

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

Đầu ra: 4

Giải thích

Tàu 1: dừng bến 2 - 09:15-09:30
Tàu 2: dừng bến 1 - 09:30-09:45
Tàu 3: KHÔNG dừng
Tàu 4: dừng bến 3 - 09:10-09:25
Tàu 5: dừng bến 1 - 09:40-10:15

Phương pháp giải

Dùng tham lam (greedy) - chọn hoạt động (activity selection) cho mỗi bến. Tạo vector cho mỗi bến lưu thông tin tàu, sắp xếp và chọn tối ưu.

Ví dụ

#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, T = 5;
    int trains[T][3] = {{915, 930, 2}, {930, 945, 3}, {930, 1200, 1}, {910, 925, 3}, {940, 1015, 1}};
    cout << "Số tàu tối đa dừng tại trạm: " << maxStop(trains, N, T);
    return 0;
}

Đầu ra

Số tàu tối đa dừng tại trạm: 4