Maximize the number of TV shows that can be watched


  • 1
    P

    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.


  • 0
    J

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


  • 0
    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 :)


  • 0
    R

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


  • 0
    J

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


  • 0
    P

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


  • 0
    T

    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;
        }
    

    '''


  • 1

    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)]
    

Log in to reply
 

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