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:
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:
working_intersection = temp

if working_intersection:
else:

return final_intersections

• You want to meet all your friends? In the minimum number of days? And those days need to be contiguous? – Pål GD Jul 3 at 9:16
• yeah, but you could meet 4 friends on one day, and another 3 friends on another day, etc. The segments of availability is continuous. But not the meeting days. you could meet 2 friends on 13, and 6 friends on 23, for example. – David Refaeli Jul 3 at 9:18
• In your first example, why day 4 instead of 5? Is the end of the days range exclusive? – IEatBagels Jul 3 at 17:00
• What does a segment represent? Is it when a particular friend is available? – vnp Jul 3 at 17:16
• @IEatBagels it could also be 5. There can be different solutions. What important is the number of days - in that example - you cannot meet all of them in 1 day, but you can meet all of them in 2 days. Segments are inclusive. – David Refaeli Jul 3 at 17:29

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