# Maximize the number of TV shows that can be watched

• Given a TV show guide which is a list of start and end times for each TV show being aired on a given day, return the list which has the maximize shows that can be watched without conflicts.

• @Pooja71 Scheduling problem, did you get offer? If they do, I bet they will give you option to join Alexa :P

• @JustVirtually Hi, unfortunately they felt I was better suited for a SDE1 position but did not have requirement for the same. So my profile is on hold. Thanks for asking :)

• @Pooja71 Wouldn't a greedy algorithm work for this instance?

• @rhuang97 Yes, Greedy solution will be always there for every problem. I think for the interview, DP solution is expected (to reduce the time complexity).

• @JustVirtually Can you elaborate a little more about your greedy solution?

• Correct me in below code that how to add show result to "res" list, Thanks.
'''
public List<List<int>> TVShows(List<List<int>> shows)
{
List<List<int>> res = new List<List<int>>();
for (int i = 0; i < shows.Count; i++)
{
DP(shows, i, res);
}
return res;
}

``````    private static List<List<int>> DP(List<List<int>> shows, int show, List<List<int>> res)
{

for (int i = show; i < shows.Count; i++)
{
if (i < shows.Count - 1 && shows[i][1] <= shows[i + 1][0])
{
DP(shows, i + 1, res);
}
else if(i == shows.Count)
{
}
}

return res;
}
``````

'''

• Greedy approach:

``````programming = [(8, 11), (4, 7), (1, 4), (3, 5), (5, 9), (0, 6), (3, 8), (6, 10)]

def schedule_greedy(prog):
def not_overlap(entry1, entry2):
if entry1[0] >= entry2[1]:
return True
elif entry1[1] <= entry2[0]:
return True
else:
return False

sorted_prog = sorted(prog, key=lambda x: x[1]) # sort by end time
result = []
while sorted_prog:
smallest_entry = sorted_prog.pop(0)
result.append(smallest_entry)
sorted_prog = [entry for entry in sorted_prog if not_overlap(smallest_entry, entry)]
return result

print(schedule_greedy(programming))
# output
# [(1, 4), (4, 7), (8, 11)]
``````

Dynamic Programming approach:

``````def schedule_dp(prog):
def not_ovlp(n):
for i in range(n-1, -1, -1):
if sorted_prog[n][0] >= sorted_prog[i][1]:
return i+1
return 0

sorted_prog = sorted(prog, key=lambda x: x[1])
pn = len(sorted_prog)
dp = [[]]*(pn+1)
for i in range(1, pn+1):
r1 = dp[not_ovlp(i-1)] + [sorted_prog[i-1]]
r2 = dp[i-1]
dp[i] = r1 if len(r1) > len(r2) else r2
return dp[pn]

print(schedule_dp(programming))
# output
# [(1, 4), (4, 7), (8, 11)]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.