Weighted Job Scheduling

Problem

Given N jobs where every job is represented by following three elements of it.

Start Time
Finish Time
Profit or Value Associated
Find the maximum profit subset of jobs such that no two jobs in the subset overlap.

Code

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;
int n;
struct Job {
    int start;
    int end;
    int profit;
}job[N];
bool cmp(const Job & a,const Job & b) {
    return a.end < b.end;
}
int dp[N];

int search(int end,int pos) {
    if (job[0].end > end) {
        return -1;
    }
    int l = 0;
    int r = pos + 1;
    while (l < r) {
        int m = (l + r) / 2;
        if (job[m].end <= end) {
            l = m + 1;
        }
        else {
            r = m;
        }
    }
    return l - 1;
}

int main() {
 scanf("%d",&n);
 for (int i = 0;i < n;i ++) {
     scanf("%d%d%d",&job[i].start,&job[i].end,&job[i].profit);
 }
 sort(job,job + n,cmp);
 dp[0] = job[0].profit;
 for (int i = 1;i < n;i ++) {
     dp[i] = dp[i - 1];
     int pos = search(job[i].start,i - 1);
     if (pos != -1) {
         dp[i] = max(dp[i],dp[pos] + job[i].profit);
     }
 }
 cout << dp[n - 1] << endl;
 return 0;
}