1235. Maximum Profit in Job Scheduling Hard

1/**
2 * [1235] Maximum Profit in Job Scheduling
3 *
4 * We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].
5 * You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.
6 * If you choose a job that ends at time X you will be able to start another job that starts at time X.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2019/10/10/sample1_1584.png" style="width: 380px; height: 154px;" />
10 * 
11 * Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
12 * Output: 120
13 * Explanation: The subset chosen is the first and fourth job. 
14 * Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.
15 * 
16 * Example 2:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2019/10/10/sample22_1584.png" style="width: 600px; height: 112px;" /> 
18 * 
19 * Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
20 * Output: 150
21 * Explanation: The subset chosen is the first, fourth and fifth job. 
22 * Profit obtained 150 = 20 + 70 + 60.
23 * 
24 * Example 3:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2019/10/10/sample3_1584.png" style="width: 400px; height: 112px;" />
26 * 
27 * Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
28 * Output: 6
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
34 * 	1 <= startTime[i] < endTime[i] <= 10^9
35 * 	1 <= profit[i] <= 10^4
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/maximum-profit-in-job-scheduling/
41// discuss: https://leetcode.com/problems/maximum-profit-in-job-scheduling/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn job_scheduling(start_time: Vec<i32>, end_time: Vec<i32>, profit: Vec<i32>) -> i32 {
47        0
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_1235() {
59    }
60}
61