Find minimal number of days to meet all your friends I was asked this in an interview yesterday:

You get an array of segments (segment contains 2 numbers, representing days count (say in a month, but could be in a year, etc.): start, end). You need to find the minimum number of days where you can meet as many of your friends.

For example, if you get [2, 5], [4, 8], [6, 10] - then one possible answer would be  4 and 6. If you get [1,10], [2,9], [3,7] one possible answer would be 5, as in day 5 everyone is available and you can meet them all. 

My way of solving was to order the segments by start, and then look for the biggest intersection. Though I was told this is not the most optimal solution. So  I wonder - what is the optimal solution (i.e. more efficient)?

Here's my code:

def optimal_dates(segments):    
    # sort the segments
    sorted_segments = sorted(segments_list, key=lambda var: var[0])

    # perform actual algorithm
    final_intersections = set()         # stores the final return result
    working_intersection = set()        # stores the working accumulative intersections
    for i in range(len(sorted_segments) - 1):
        seg_b = set(range(sorted_segments[i + 1][0], sorted_segments[i + 1][1] + 1))
        if not working_intersection:
            seg_a = set(range(sorted_segments[i][0], sorted_segments[i][1] + 1))
            working_intersection = seg_a.intersection(seg_b)
            # if empty, seg_a doesn't intersects forward, so add any element from it
            if not working_intersection:
                final_intersections.add(seg_a.pop())
        else:
            temp = working_intersection.intersection(seg_b)
            # if empty, this was end of intersection, so add any element from the previous accumulative intersections
            if not temp:
                final_intersections.add(working_intersection.pop())
            working_intersection = temp

    # add the final element
    if working_intersection:
        final_intersections.add(working_intersection.pop())
    else:
        final_intersections.add(sorted_segments[-1][0])

    return final_intersections
Making the set out of an interval is an immediate red flag. set is a heavyweight data structure, and making it is a heavyweight operation. It is also much easier to compute an intersection of two intervals, than of two sets.

Making the same set twice is another red flag.



All that said, it seems that you really overthink the problem. It admits a much simpler solution. Consider the friend whose window of opportunity closes the earliest. You want to meet him anyway, so make the most of it: select every friend whose window opens prior to it, schedule a party, and discard all the participants from further consideration; rinse and repeat.

Hint: do not sort the list of intervals. Sort the list of events (interval openings and closings).

Two things I intentionally don't want to spell out:


Prove that this algorithm does produce an optimal solution, and
How to efficiently discard the friends you've already met.