algo-aha

需要最少多少区间来覆盖某范围

• https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/
• https://leetcode.com/problems/video-stitching/

int videoStitching(vector<vector<int>>& clips, int T) {
    const int N = clips.size();
    sort(begin(clips), end(clips));
    int i = 0, ans = 0;
    int sofar = 0; // 当前已覆盖[..sofar]区间
    int frontier = 0; // 尝试扩展当前区间
    while (sofar < T) {
        while (i < N && clips[i][0] <= sofar) {
            frontier = max(frontier, clips[i][1]);
            i++;
        }
        if (frontier == sofar) return -1;
        sofar = frontier;
        ans++;
    }
    return ans;
}

或者

int videoStitching(vector<vector<int>>& clips, int T) {
    // 实际是bfs分层遍历
    const int N = clips.size();
    sort(begin(clips), end(clips));
    int ans = 0;
    int frontier = 0;
    // 若还有扩展可能，类似 while (!q.empty())
    for (int i = 0; i < N && clips[i][0] <= frontier; ) { 
        ans++;
        // 扩展一层，类似 for (int sz=q.size(); sz > 0; sz--)
        for (int sofar = frontier; i < N && clips[i][0] <= sofar; i++) { 
            frontier = max(frontier, clips[i][1]);
            if (frontier >= T) return ans;
        }
    }
    return -1;
}

最少跳跃

• https://leetcode.com/problems/jump-game-ii/

int jump(vector<int>& nums) {
	// 点i覆盖[i,i+nums[i]]，需要到覆盖[0,N-1]
	const int N = nums.size();
	if (N <= 1) return 0;

	// 实际是bfs分层遍历
	int ans = 0;
	for (int i = 0, hi = 0; i <= hi;) {
		ans++; // 在nums[i]处跳
		int hi0 = hi;
		for (; i <= hi0; i++) {
			hi = max(hi, i + nums[i]);
			if (hi >= N - 1) return ans;
		}
	}
	return -1;
}

若只问能否跳跃到达，不用分层遍历

• https://leetcode.com/problems/jump-game/

bool canJump(vector<int>& nums) {
	const int N = nums.size();
	for (int i = 0, hi = 0; i <= hi; i++) {
		hi = max(hi, i + nums[i]);
		if (hi >= N - 1) return true;
	}
	return false;
}