Note: This article is available in Chinese only. 本文暂无英文版本。
View original
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
思路:dp[i]表示能否到达位置i…无脑dp即可。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月11日 星期二 19时33分51秒
4File Name :55.cpp
5************************************************ */
6class Solution {
7
8public:
9
10 bool canJump(vector<int>& nums) {
11 int n = nums.size();
12 if (n==0) return false;
13 vector<int>dp(n,false);
14 dp[0] = true;
15 for ( int i = 0 ; i < n ; i++)
16 {
17 if (dp[i])
18 {
19 int r = min(i+nums[i],n-1);
20 for ( int j = i+1 ; j <=r ; j++)
21 dp[j] = true;
22 }
23 }
24 return dp[n-1];
25
26
27 }
28
29};