主題
題目: 1235. Maximum Profit in Job Scheduling
難度: Hard
目前下列解法的時間複雜度: O(n*lg(n))
題目說明
現在有好多1維整數上的區間(左界有包含，右界不包含)，區間左界端點 > 0 ，區間上有一正整數 < 10001 ，
問若從這些區間中選定一些區間，這些區間互不重疊，則區間上的正整數相加最大是多少。
解法: 套自己的模板好爽喔，然後好慢喔
0. 一開始先加一個最右邊的區間，左界 > 其他所有區間的右界，左界 = 右界，區間上的正整數 = 0 。
1. 以區間左界對區間排序。
2. 依大小整理好不同的左界及右界，要做到可以很快轉換成所有左界及右界一起排序後的順序。
3. 建一棵假線段樹，operator是max
4. 依步驟1.排序後的順序由小到大更新答案:
a. 在左界變化之前，在此之前的正整數加總最大值先不要更新假線段樹。
b. 在左界變化之後的一開始，之前看過但沒更新假線段樹的正整數加總，現在更新。
c. 對每個區間，只要問這棵假線段樹0至此區間排序後順序的位置+1 (不含) 當中最大的是多少， 加上此區間上的正整數 後填到此區間右界排序後順序位置的答案上。
5. 拿步驟0.所加區間的右界排序位置的答案回傳。
source code
別人的答案總是比我簡單 QAQ
噢耶，跟上一篇解法好像喔
難度: Hard
目前下列解法的時間複雜度: O(n*lg(n))
題目說明
現在有好多1維整數上的區間(左界有包含，右界不包含)，區間左界端點 > 0 ，區間上有一正整數 < 10001 ，
問若從這些區間中選定一些區間，這些區間互不重疊，則區間上的正整數相加最大是多少。
解法: 套自己的模板好爽喔
0. 一開始先加一個最右邊的區間，左界 > 其他所有區間的右界，左界 = 右界，區間上的正整數 = 0 。
1. 以區間左界對區間排序。
2. 依大小整理好不同的左界及右界，要做到可以很快轉換成所有左界及右界一起排序後的順序。
3. 建一棵假線段樹，operator是max
4. 依步驟1.排序後的順序由小到大更新答案:
a. 在左界變化之前，在此之前的正整數加總最大值先不要更新假線段樹。
b. 在左界變化之後的一開始，之前看過但沒更新假線段樹的正整數加總，現在更新。
c. 對每個區間，只要問這棵假線段樹0至此區間排序後順序的位置+1 (不含) 當中最大的是多少， 加上此區間上的正整數 後填到此區間右界排序後順序位置的答案上。
5. 拿步驟0.所加區間的右界排序位置的答案回傳。
source code
別人的答案總是比我簡單 QAQ
