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;
}