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) # 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], sorted_segments[i + 1] + 1)) if not working_intersection: seg_a = set(range(sorted_segments[i], sorted_segments[i] + 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]) return final_intersections