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.
Maximize the number of TV shows that can be watched

@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 :)


@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).


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) { res.Add(shows[i]); } } 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(n1, 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(i1)] + [sorted_prog[i1]] r2 = dp[i1] dp[i] = r1 if len(r1) > len(r2) else r2 return dp[pn] print(schedule_dp(programming)) # output # [(1, 4), (4, 7), (8, 11)]