Find minimal number of days to meet all your friends

Question

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

Answer 1

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:

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

Answer 2

You can find the minimal amounts by segregating each key:value where the key is days and values are people:

ls = [[2,4], [3, 9], [4,9], [9, 3]] # your data
print(ls)
ns = {days: people-days for days, people in ls if days < people} 
print(ns)

This returns:

[[2, 4], [3, 9], [4, 9], [9, 3]]
{2: 2, 3: 6, 4: 5} # value is now the difference between days and people

From here you can see the largest difference which will be your minimal and maximum.