# 1235. Maximum Profit in Job Scheduling
###### tags: `Leetcode` `Medium` `Greedy` `Intervals`
Link: https://leetcode.com/problems/maximum-profit-in-job-scheduling/description/
## 思路
和[2008. Maximum Earnings From Taxi](https://hackmd.io/uszy0XX3SOSyAB754hXTbw)题意差不多
但是由于starttime和endtime最大是$10^9$ 同样的方法做会TLE

思路[参考](https://leetcode.com/problems/maximum-profit-in-job-scheduling/description/)
考虑到我们最终选取的区间必须是non-overlapping的，所以根据经验，我们按照```endTime```对区间进行排序

有点像背包问题
对于每个job
我们可以用这个job 那就是找到小于等于当前job startTime的entry里面最大的key 再加上当前job的profit就是job 的endTime所对应的profit
也可以不选任何在当前位置结束的job
我们可以用treeMap实现这件事 对于每一个新进来的job(它的endTime一定大于等于map里面的所有key) 
如果它的profit比现在map里面最后一个entry的value小 我们就不把它加在map里面
否则就加进去
这样做的结果就是map里面的所有entry的value是递增的
那么结果就是最后一个entry的value
## Code

class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int n = startTime.length;
List<int[]> jobs = new ArrayList<>();
for(int i=0; i<n; i++){
jobs.add(new int[]{startTime[i], endTime[i], profit[i]});
}
Collections.sort(jobs, (a,b)->(a[1]-b[1]));
TreeMap<Integer, Integer> map = new TreeMap<>();
map.put(0,0);
for(int i=0; i<n; i++){
int[] cur = jobs.get(i);
int p = map.floorEntry(cur[0]).getValue()+cur[2];
if(p > map.lastEntry().getValue()){
map.put(cur[1], p);
}
}
return map.lastEntry().getValue();
}
}