Python Complete Search In One Pass Function

I am writing a program that takes in a list of start and end times for farmers milking cows and determines both the longest time where >=1 cow is being milked and the longest ti

Solution 1:

Here is a very straightforward approach which does it in one pass, including a sort, so the complexity would be O(n*logn).

# Part 1: transform to tuples (start_time, typ)
items = []
for start, end in times:
    items += [(start, 's'), (end, 'e')]
items = sorted(items)

# Part 2: compute max durations where 0 or 1+ cows are being milked
max_0_cows = max_1plus_cows = 0

last_intersection_time = items[0][0] # starting with first cow milk time
nof_cows_milked = 1for i, (start_time, typ) inenumerate(items[1:], 1):
    if items[i-1][0] == start_time and items[i-1][1] != typ:
        continueif i+1 < len(items) and items[i+1][0] == start_time and items[i+1][1] != typ:
        continueif typ == 's':
        nof_cows_milked += 1elif typ == 'e':
        nof_cows_milked -= 1# check if we cross from 1+ -> 0 or 0 -> 1+if (typ, nof_cows_milked) in (('e', 0), ('s', 1)):
        duration = start_time - last_intersection_time
        if nof_cows_milked == 1:
            max_0_cows = max(max_0_cows, duration)
        if nof_cows_milked == 0:
            max_1plus_cows = max(max_1plus_cows, duration)
        last_intersection_time = start_time

print("Max time 0 cows: {}, Max time 1+ cows: {}".format(max_0_cows, max_1plus_cows))

1. Building of items: It puts the start/end itervals into a list of tuples (start_time, typ) so we can traverse the list and if we see a s a new cow is being milked and e then a cow is stopped being milked. This way we can have a counter nof_cows_milked at any time which is the basis for getting the "max time 0 cows milked" and "max time 1+ cows milked"
2. The actual longest-time-finder checks for all the transitions from 0 -> 1+ cows milked or 1+ cows -> 0 cows milked. In the first 4 lines it filters out the cases when two adjacent itervals (one farmer stops when the other farmer starts) It keeps track of those times with last_intersection_time and compares the duration to the max duration of max_0_cows and max_1_plus_cows. Again, this part is not very pretty, maybe there are more elegant ways to solve that.

[my algorithm] gives the wrong output [...] and I'm confused as to why

Your algorithm basically just checks for the longest interval of a single tuple, but doesn't check for overlapping or adjacent tuples.

Take these intervals as an visual example:

Your code just finds the interval G-H, whereas you need to find C-F. You somewhere need to keep track of how many cows are milked in parallel, so you need at least the nof_of_cows_milked counter as in my code example.