<p>We have <code>n</code> jobs, where every job is scheduled to be done from <code>startTime[i]</code> to <code>endTime[i]</code>, obtaining a profit of <code>profit[i]</code>.</p>

<p>You&#39;re given the <code>startTime</code>, <code>endTime</code> and <code>profit</code> arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.</p>

<p>If you choose a job that ends at time <code>X</code> you will be able to start another job that starts at time <code>X</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/10/10/sample1_1584.png" style="width: 380px; height: 154px;" /></strong></p>

<pre>
<strong>Input:</strong> startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
<strong>Output:</strong> 120
<strong>Explanation:</strong> The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/10/10/sample22_1584.png" style="width: 600px; height: 112px;" /> </strong></p>

<pre>
<strong>Input:</strong> startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
<strong>Output:</strong> 150
<strong>Explanation:</strong> The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.
</pre>

<p><strong class="example">Example 3:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/10/10/sample3_1584.png" style="width: 400px; height: 112px;" /></strong></p>

<pre>
<strong>Input:</strong> startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
<strong>Output:</strong> 6
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= startTime.length == endTime.length == profit.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= startTime[i] &lt; endTime[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= profit[i] &lt;= 10<sup>4</sup></code></li>
</ul>

// // #include <iostream>
// // #include <vector>
// // #include <algorithm>
// // #include <tuple>

// // using namespace std;
// // class Solution {
// // public:
// //     int fun2(int i, vector<int>& prof, vector<vector<int>> &jobs, vector<int> &dp,vector<int>& start) {
// //         if (i == prof.size()) return 0;
// //         if(dp[i] != -1)return dp[i];
// //         int not_pick = fun2(i+1, prof, jobs,dp,start);
// //         int st = jobs[i][0];
// //         int end = jobs[i][1];
// //         auto idx = lower_bound(start.begin(), start.end(), end) - start.begin();
// //         int pick = jobs[i][2];
// //         if (idx < prof.size()) pick += fun2(idx, prof, jobs,dp,start);
// //         return dp[i] = max(pick, not_pick);
// //     }

// //     int jobScheduling(vector<int>& st, vector<int>& et, vector<int>& prof) {
// //         int n = st.size();
// //         vector<vector<int>> jobs;
// //         for (int i = 0; i < n; i++) {
// //             jobs.push_back({st[i], et[i], prof[i]});
// //         }
// //         sort(jobs.begin(), jobs.end());
// //         sort(st.begin(), st.end());
// //         vector<int> dp(n,-1);
// //         return fun2(0, prof, jobs,dp,st);
// //     }
// // };
// #include <bits/stdc++.h>
// class Solution {
// public:
//     int jobScheduling(vector<int>& st, vector<int>& et, vector<int>& prof) {
//         int n = st.size();
//         vector<vector<int>> jobs;

//         // Create jobs vector with start, end, and profit
//         for (int i = 0; i < n; i++) {
//             jobs.push_back({st[i], et[i], prof[i]});
//         }
        
//         // Sort jobs based on their start time
//         sort(jobs.begin(), jobs.end());
//         sort(st.begin(), st.end());

//         vector<int> dp(n, 0); // dp[i] will store the maximum profit until job i
//         dp[n - 1] = jobs[n - 1][2]; // The last job's profit is its own profit

//         // Iterate over all jobs from n-2 to 0
//         for (int i = n - 2; i >= 0; i--) {
//             int st = jobs[i][0];
//             int end = jobs[i][1];
//             int prof = jobs[i][2];

//             // Find the next job that starts after this job ends
//             auto idx = lower_bound(st.begin(), st.end(), end) - st.begin();

//             // If there is a valid next job, add its profit
//             int pick = prof;
//             if (idx < n) pick += dp[idx];

//             // Max of picking this job or not picking it
//             dp[i] = max(pick, dp[i + 1]);
//         }

//         // The maximum profit is stored at dp[0]
//         return dp[0];
//     }
// };

// // int main() {
// //     Solution sol;
// //     vector<int> start = {1, 2, 3, 4, 6};
// //     vector<int> end = {3, 5, 10, 6, 9};
// //     vector<int> profit = {20, 20, 100, 70, 60};
// //     cout << sol.jobScheduling(start, end, profit) << endl; // Output: 150
// //     return 0;
// // }

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int jobScheduling(vector<int>& startTimes, vector<int>& endTimes, vector<int>& profits) {
        int n = startTimes.size();
        vector<vector<int>> jobs;

        // Create jobs vector with start, end, and profit
        for (int i = 0; i < n; i++) {
            jobs.push_back({startTimes[i], endTimes[i], profits[i]});
        }
        
        // Sort jobs based on their start time
        sort(jobs.begin(), jobs.end());

        // Extract the sorted start times for binary search
        vector<int> sortedStartTimes;
        for (int i = 0; i < n; i++) {
            sortedStartTimes.push_back(jobs[i][0]);
        }

        vector<int> dp(n, 0); // dp[i] will store the maximum profit until job i
        dp[n - 1] = jobs[n - 1][2]; // The last job's profit is its own profit

        // Iterate over all jobs from n-2 to 0
        for (int i = n - 2; i >= 0; i--) {
            int start = jobs[i][0];
            int end = jobs[i][1];
            int profit = jobs[i][2];

            // Find the next job that starts after this job ends
            auto idx = lower_bound(sortedStartTimes.begin(), sortedStartTimes.end(), end) - sortedStartTimes.begin();

            // If there is a valid next job, add its profit
            int pick = profit;
            if (idx < n) pick += dp[idx];

            // Max of picking this job or not picking it
            dp[i] = max(pick, dp[i + 1]);
        }

        // The maximum profit is stored at dp[0]
        return dp[0];
    }
};

// int main() {
//     Solution sol;
//     vector<int> start = {1, 2, 3, 4, 6};
//     vector<int> end = {3, 5, 10, 6, 9};
//     vector<int> profit = {20, 20, 100, 70, 60};
//     cout << sol.jobScheduling(start, end, profit) << endl; // Output: 150
//     return 0;
// }

97696