#include <stdio.h>
#include <stdlib.h>
typedef struct { int start, end, value; } Interval;
int cmp(const void *a, const void *b) {
return ((Interval*)a)->end - ((Interval*)b)->end;
}
int binarySearch(Interval intervals[], int index) {
int lo = 0, hi = index - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (intervals[mid].end <= intervals[index].start) {
if (intervals[mid + 1].end <= intervals[index].start) lo = mid + 1;
else return mid;
} else hi = mid - 1;
}
return -1;
}
int weightedIntervalScheduling(Interval intervals[], int n) {
qsort(intervals, n, sizeof(Interval), cmp);
int dp[n + 1];
dp[0] = 0;
for (int i = 1; i <= n; i++) {
int inclProfit = intervals[i-1].value;
int l = binarySearch(intervals, i-1);
if (l != -1) inclProfit += dp[l+1];
dp[i] = (inclProfit > dp[i-1]) ? inclProfit : dp[i-1];
}
return dp[n];
}
int main() {
Interval intervals[] = {{1,2,100}, {2,5,200}, {3,6,300}, {4,8,400}, {5,9,500},
{6,10,100}};
int n = sizeof(intervals) / sizeof(intervals[0]);
printf("Maximum profit: %d\n", weightedIntervalScheduling(intervals, n));
return 0;
}