5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You want to meet all your friends? In the minimum number of days? And those days need to be contiguous? \$\endgroup\$ – Pål GD Jul 3 at 9:16
  • \$\begingroup\$ 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. \$\endgroup\$ – David Refaeli Jul 3 at 9:18
  • \$\begingroup\$ In your first example, why day 4 instead of 5? Is the end of the days range exclusive? \$\endgroup\$ – IEatBagels Jul 3 at 17:00
  • \$\begingroup\$ What does a segment represent? Is it when a particular friend is available? \$\endgroup\$ – vnp Jul 3 at 17:16
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – David Refaeli Jul 3 at 17:29
3
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.