最多区间个数
贪心算法
arr[[start, end]] 按照 end 排序
从 i = 0 开始，逐个加入区间，如果当前区间和已选择的区间都不重叠，则加入该区间，否则跳过
动态规划
同样的先按照 end 字段排序，dp[i] 表示前 i 个区间的最多区间个数，则有： 初始状态： dp[0] = 1 (加入了第一个区间) 最优解中不包括第 i+1 个区间 dp[i+1] = dp[i] (因为 dp 是非递减数组，所以取最大的那个，也就是前一个最优解) 最优解中包括第 i+1 个区间，而且第 i+1 个区间之前存在非重叠区间 dp[i+1] = dp[k] + 1, k 是从 i 到 0 与arr[i+1]不重叠的第一个区间 所以，dp[i+1] 是以上两种情况的最大值
最长区间总数
动态规划
和最多区间个数的求解方法类似： dp[0] = arr[0][1] - arr[0][0] dp[i+1] = dp[i] dp[i+1] = dp[k] + (arr[i+1][1] - arr[i+1][0]) dp[i+1] = arr[i+1][1] - arr[i+1][0]
加权最长区间总数
动态规划
dp[0] = (arr[0][1] - arr[0][0]) * v[0] dp[i+1] = dp[i] dp[i+1] = dp[k] + (arr[i+1][1] - arr[i+1][0]) * v[i+1] dp[i+1] = (arr[i+1][1] - arr[i+1][0]) * v[i+1]
