#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct XeKhach {
    string tenChu;
    int soGhe;
    int tienVe;
};

bool soSanhTheoTienVeGiamDan(const XeKhach &a, const XeKhach &b) {
    return a.tienVe > b.tienVe;
}

bool soSanhTheoSoGheTangDan(const XeKhach &a, const XeKhach &b) {
    return a.soGhe < b.soGhe;
}

int main() {
    vector<XeKhach> d = {
        {"Nguyen Van A", 16, 5},
        {"Tran Thi B", 29, 8},
        {"Le Van C", 45, 12},
        {"Pham Thi D", 32, 10},
        {"Hoang Van E", 25, 7},
        {"Vu Thi F", 18, 6},
        {"Do Van G", 36, 11}
    };

    int m = 30; // Tổng tiền vé yêu cầu tối thiểu (đơn vị: trăm nghìn)
    int v = 50; // Sức chứa nhà chờ (tổng số ghế tối đa)

    // =============================
    // Yêu cầu 1: Tìm số xe ít nhất để tổng tiền > m
    // =============================
    sort(d.begin(), d.end(), soSanhTheoTienVeGiamDan);

    int tongTien = 0;
    int soXeCanDung = 0;

    for (const auto &xe : d) {
        tongTien += xe.tienVe;
        soXeCanDung++;
        if (tongTien > m) break;
    }

    cout << "1. So xe can dung de tong tien > " << m << " la: " << soXeCanDung << endl;

    // =============================
    // Yêu cầu 2: Chọn xe vào nhà chờ để tong tien max nhưng tong ghe <= v
    // (Bài toán giống ba lô 0-1)
    // =============================

    int n = d.size();
    sort(d.begin(), d.end(), soSanhTheoSoGheTangDan); // sắp theo số ghế để dễ debug

    vector<vector<int>> dp(n + 1, vector<int>(v + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= v; j++) {
            if (d[i-1].soGhe <= j) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - d[i-1].soGhe] + d[i-1].tienVe);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    cout << "2. Tong tien toi da trong gioi han suc chua " << v << " la: " << dp[n][v] << endl;

    return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct CuocHop {
    int batDau, ketThuc, chiPhi;
};

// Hàm so sánh để sắp theo thời gian kết thúc (dùng cho greedy)
bool soSanhKetThuc(const CuocHop &a, const CuocHop &b) {
    return a.ketThuc < b.ketThuc;
}

// Tìm cuộc họp gần nhất không trùng thời gian (kết thúc <= bắt đầu hiện tại)
int timCuocHopTruoc(const vector<CuocHop>& ds, int i) {
    int l = 0, r = i - 1, kq = -1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (ds[m].ketThuc <= ds[i].batDau) {
            kq = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return kq;
}

int main() {
    vector<CuocHop> ds = {
        {1, 3, 50},
        {3, 5, 20},
        {0, 6, 100},
        {5, 7, 30},
        {5, 9, 60},
        {7, 8, 25},
        {8, 11, 55},
        {2, 13, 75}
    };

    int n = ds.size();

    // ======= Câu 1: Tối đa số lượng cuộc họp (Greedy) =======
    sort(ds.begin(), ds.end(), soSanhKetThuc);

    int dem = 0, ketThucGanNhat = -1;

    for (const auto &hop : ds) {
        if (hop.batDau >= ketThucGanNhat) {
            dem++;
            ketThucGanNhat = hop.ketThuc;
        }
    }

    cout << "1. So cuoc hop nhieu nhat co the to chuc la: " << dem << endl;

    // ======= Câu 2: Tối đa tổng chi phí thu được (Quy hoạch động) =======
    vector<int> dp(n, 0);

    dp[0] = ds[0].chiPhi;

    for (int i = 1; i < n; i++) {
        int chon = ds[i].chiPhi;
        int truoc = timCuocHopTruoc(ds, i);
        if (truoc != -1)
            chon += dp[truoc];

        dp[i] = max(dp[i - 1], chon);
    }

    cout << "2. Tong tien thu nhieu nhat co the dat duoc la: " << dp[n - 1] << endl;

    return 0;
}