Problem 53: Weighted Interval Scheduling
Problem Statement: Given a set of intervals each with a start time, end time, and a profit, select a subset of non-overlapping intervals maximizing total profit.
Input
The first line contains an integer n. Each of the next n lines contains three integers: start time, end time and profit.
Output
Print the maximum total profit from non-overlapping intervals.
Examples
Input:
4
1 3 50
3 5 20
6 19 100
2 100 200
Output:
250
Solution Explanation
Sort intervals by end time. Use dynamic programming with binary search to find the last interval that doesn't conflict with the current interval. Transition DP[i] = max(DP[i-1], profit[i] + DP[index]).
Solution in C++
#include
#include
#include
using namespace std;
struct Interval {
int s, e, p;
};
bool cmp(const Interval &a, const Interval &b) {
return a.e < b.e;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector arr(n);
for(int i = 0; i < n; i++){
cin >> arr[i].s >> arr[i].e >> arr[i].p;
}
sort(arr.begin(), arr.end(), cmp);
vector dp(n, 0);
dp[0] = arr[0].p;
for(int i = 1; i < n; i++){
int incl = arr[i].p;
int l = 0, r = i - 1, pos = -1;
while(l <= r){
int mid = (l + r) / 2;
if(arr[mid].e <= arr[i].s){
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
if(pos != -1) incl += dp[pos];
dp[i] = max(dp[i-1], incl);
}
cout << dp[n-1] << "\n";
return 0;
}