Max Programs a student can attend ?

A college organized various training programs for students. Each program has the following fields ,

[Program name][Start Time][End Time] [program Value].

These details were stored in a vector of string.

Find out how many program a students attends to maximize his/her total program value.

Input :

4 -> Number of Program scheduled in a day;

[P1] [14][15][200] // 14 implies 1400 or 2pm;

[p2][18][19][200]

[p3][16][19][100]

[p4][15][18][100]

Output:

(P1->P4->P2)

Solution:

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

struct Program {
    std::string name;
    int start;
    int end;
    int value;

    Program(const std::string& n, int s, int e, int v) : name(n), start(s), end(e), value(v) {}
};

bool sortByEndTime(const Program& p1, const Program& p2) {
    return p1.end < p2.end;
}

int maxPrograms(std::vector<Program>& programs) {
    int n = programs.size();
    if (n <= 1) {
        return n; // If there's only one or no program, return its count
    }

    // Sort programs by end times
    std::sort(programs.begin(), programs.end(), sortByEndTime);

    // Initialize variables
    int totalValue = programs[0].value;
    int count = 1;

    // Iterate through the sorted programs
    int lastEndTime = programs[0].end;
    for (int i = 1; i < n; ++i) {
        if (programs[i].start >= lastEndTime) {
            // Select the program if its start time is after or equal to the end time of the last selected program
            totalValue += programs[i].value;
            lastEndTime = programs[i].end;
            count++;
        }
    }

    return count;
}

int main() {
    // Example usage:
    std::vector<Program> programs = {
        {"P1", 14, 15, 200},
        {"P2", 18, 19, 200},
        {"P3", 16, 19, 100},
        {"P4", 15, 18, 100}
    };

    int result = maxPrograms(programs);

    std::cout << "Maximum programs a student can attend: " << result << std::endl;

    return 0;
}