Find maximum nonoverlapping intervals


  • 2
    R

    Given a list of intervals of time, find the set of maximum non-overlapping intervals.

    For example,

    given following intervals:
    
    [0600, 0830], [0800, 0900], [0900, 1100], [0900, 1130], 
    [1030, 1400], [1230, 1400]
    
    Also it is given that time have to be in the range [0000, 2400].
    
    The maximum non-overlapping set of intervals is [0600, 0830], [0900, 1130], [1230, 1400].

  • 4

    I guess we can just use greedy algorithm, first sort the intervals by finish time, pick the first interval, for the remaining intervals, go through each one of them, as long as the start time is greater than the last selected finish time, add it to the final result. Eventually you will get the longest non-overlapping set of intervals.


  • 1
    W

    a follow up question I encountered during interview is: "if each interval has assigned weight, what's the max weight for nonoverlapping intervals you can get?" Then it becomes a DP problem.


Log in to reply
 

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