You are given a series of video clips from a sporting event that lasted T seconds.  These video clips can be overlapping with each other and have varied lengths.
Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1].  We can cut these clips into segments freely: for example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].
Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event ([0, T]).  If the task is impossible, return -1.
 
Example 1:
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
Output: 3
Explanation: 
We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

Example 2:
Input: clips = [[0,1],[1,2]], T = 5
Output: -1
Explanation: 
We can't cover [0,5] with only [0,1] and [1,2].

Example 3:
Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
Output: 3
Explanation: 
We can take clips [0,4], [4,7], and [6,9].

Example 4:
Input: clips = [[0,4],[2,8]], T = 5
Output: 2
Explanation: 
Notice you can have extra video after the event ends.

 
Constraints:

1 <= clips.length <= 100
0 <= clips[i][0] <= clips[i][1] <= 100
0 <= T <= 100

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Greedy algorithms

Starter code: class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        

Solutions:
class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		clips.sort(key=lambda x: [x[0], -x[1]])
		res = 0
		r = 0
		new_r = 0
		for (s, e) in clips:
			if s <= r:
				new_r = max(new_r, e)
			elif s > new_r:
				return -1
			else:
				res += 1
				r = new_r
				new_r = max(new_r, e)
			if new_r >= T:
				break
		if new_r < T:
			return -1
		if r < T and new_r >= T:
			res += 1
		return res


class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		last_end = 0
		clip_count = 0
		while last_end < T:
			if clip_count >= len(clips):
				return -1
			max_end = -1
			for clip in clips:
				if clip[0] <= last_end:
					if clip[1] > max_end:
						max_end = clip[1]
			if max_end >= 0:
				last_end = max_end
				clip_count += 1
			else:
				return -1
		return clip_count


class Solution:

	def videoStitching(self, clips, T):
		(end, end2, res) = (-1, 0, 0)
		for (i, j) in sorted(clips):
			if end2 >= T or i > end2:
				break
			elif end < i <= end2:
				(res, end) = (res + 1, end2)
			end2 = max(end2, j)
		return res if end2 >= T else -1


class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		dp = [T + 1] * (T + 1)
		dp[0] = 0
		i = 1
		while i <= T and dp[i - 1] < T:
			for c in clips:
				if c[0] <= i and i <= c[1]:
					dp[i] = min(dp[i], dp[c[0]] + 1)
			i += 1
		return dp[T] if dp[T] != T + 1 else -1


class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		clips.sort(key=lambda x: x[0])
		n = len(clips)
		memo = {}

		def recur(i, interval):
			if (i, interval) in memo:
				return memo[i, interval]
			if interval >= T:
				return 0
			if i == n:
				return sys.maxsize
			if interval >= clips[i][0] and interval < clips[i][1]:
				ans = min(recur(i + 1, clips[i][1]) + 1, recur(i + 1, interval))
			else:
				ans = recur(i + 1, interval)
			memo[i, interval] = ans
			return ans
		fnl = recur(0, 0)
		return -1 if fnl == sys.maxsize else fnl


class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		dp = [T + 1] * (T + 1)
		dp[0] = 0
		for i in range(1, T + 1):
			if dp[i - 1] >= T:
				break
			for (start, end) in clips:
				if start <= i <= end:
					dp[i] = min(dp[i], dp[start] + 1)
					print(dp)
		if dp[T] == T + 1:
			return -1
		else:
			return dp[T]


class Solution:
	import json

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		IMPOSSIBLE = float('inf')
		sorted_clips = sorted(clips, key=lambda x: x[0], reverse=False)
		opt = {}
		for (index, clip) in enumerate(sorted_clips):
			for t in range(0, T + 1):
				(start, end) = tuple(clip)
				if t == 0:
					opt[index, t] = 0
				elif index == 0:
					opt[index, t] = 1 if start == 0 and t <= end else IMPOSSIBLE
				else:
					opt[index, t] = min(opt[index - 1, t], opt[index - 1, min(start, t)] + 1 if t <= end else IMPOSSIBLE)
		print(opt)
		return opt[len(clips) - 1, T] if opt[len(clips) - 1, T] != float('inf') else -1


class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		clips.sort()
		n = len(clips)
		dp = [float('inf')] * (T + 1)
		dp[0] = 0
		for i in range(1, T + 1):
			for j in range(n):
				if clips[j][0] <= i <= clips[j][1]:
					dp[i] = min(dp[i], 1 + dp[clips[j][0]])
		if dp[T] == float('inf'):
			return -1
		return dp[-1]


class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		clips.sort()
		i = 0
		end = 0
		res = 0
		while end < T:
			current_end = 0
			while i < len(clips) and clips[i][0] <= end:
				current_end = max(current_end, clips[i][1])
				i += 1
			if current_end <= end:
				return -1
			end = current_end
			res += 1
		return res


class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		(end, end2, cnt) = (-1, 0, 0)
		for (s, e) in sorted(clips):
			if end2 >= T or s > end2:
				break
			elif end < s <= end2:
				cnt += 1
				end = end2
			end2 = max(end2, e)
		return cnt if end2 >= T else -1


class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		step = 0
		(l, r) = (-1, 0)
		for (i, j) in sorted(clips):
			if r >= T:
				return step
			if i > r:
				return -1
			if l < i <= r:
				step += 1
				l = r
			r = max(r, j)
		return step if r >= T else -1


class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		dp = [float(inf)] * 101
		clips.sort()
		if clips[0][0] > 0:
			return -1
		dp[0] = 0
		for i in range(len(clips)):
			clip = clips[i]
			if clip[0] != 0 and dp[clip[0]] == float(inf):
				break
			min_so_far = dp[clip[0]]
			for k in range(clip[0], clip[1] + 1):
				dp[k] = min(dp[k], min_so_far + 1)
		if dp[T] == inf:
			return -1
		return dp[T]


import math

class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		clips.sort()
		longest = sorted(clips, key=lambda a: a[1])[-1][1]
		memo = [[None for i in range(longest + 1)] for i in range(len(clips))]

		def dp(i, start):
			if start >= T:
				return 0
			curr = clips[i]
			if curr[0] > start:
				return math.inf
			elif i == len(clips) - 1:
				if curr[1] < T:
					return math.inf
				return 1
			if memo[i + 1][curr[1]] == None:
				memo[i + 1][curr[1]] = dp(i + 1, curr[1])
			if memo[i + 1][start] == None:
				memo[i + 1][start] = dp(i + 1, start)
			return min(1 + memo[i + 1][curr[1]], memo[i + 1][start])
		res = dp(0, 0)
		return res if res != math.inf else -1


class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		table = [101] * 101
		table[0] = 0
		changed = True
		while changed:
			changed = False
			for (i, j) in clips:
				for k in range(i, j + 1):
					if table[i] + 1 < table[k]:
						table[k] = table[i] + 1
						changed = True
		if table[T] < 101:
			return table[T]
		else:
			return -1


class Solution:

	def videoStitching(self, clips: List[List[int]], T: int) -> int:
		clips.sort(key=lambda x: x[0])
		dp = [[0] * (len(clips) + 1)] + [[float('inf')] * (len(clips) + 1) for _ in range(T)]
		for row in range(1, len(dp)):
			for col in range(1, len(dp[0])):
				dp[row][col] = dp[row][col - 1]
				if clips[col - 1][0] <= row - 1 < clips[col - 1][1]:
					dp[row][col] = min(dp[row][col], 1 + dp[clips[col - 1][0]][col])
		ans = dp[-1][-1] if dp[-1][-1] != float('inf') else -1
		return ans