Job Schedule with Weights

[Questions]
Given a set of jobs in the format of {start, end, weight}, where "start" is starting time, "end" is ending time, find the maximum sum of weights of non-overlapping jobs.

[Analysis]
Sort the Jobs by the ending points. Suppose Cost[i] is the maximum sum of weights of Job[0] ... Job[i],
      Cost[i+1] = max( Cost[j] + Job[i+1] ),   // where j is the last Job not overlapping with Job[i+1]
                                  Cost[i] );                     // Job[i+1] is not selected.

Padding Cost[] with an extra element at the beginning to handle the case where Job[i+1] overlaps with all previous jobs.

[Solution]
struct Job {
    int start;
    int end;
    int cost;

};

int max_cost_subset (vector<Job> &jobs ) {

    auto comp = [](Job a, Job b) { return a.end < b.end; };

    sort(jobs.begin(), jobs.end(),  comp );

    vector<int> cost(jobs.size()+1, 0);

    cost[0] = 0;

    for (int i=0; i<jobs.size(); i++ ) {

       Job tmp = jobs[i];

       swap(tmp.start, tmp.end);

       auto it = upper_bound(jobs.begin(), jobs.begin()+i+1, tmp, comp);  // -- Binary Search

       cost[i+1] = max( cost[it-jobs.begin() ] + jobs[i].cost, cost[i] );  

    }

    return cost.back();

}