Smallest difference between two time values

Question

I need some help with a coding problem.

Given a sequence of clock time values in hh:mm format, find the smallest difference in terms of minutes, between any two time values.

For example, consider the following sequences of values:

1. input = ['01:00','01:25'], smallest difference = 25 minutes

2. input = ['11:00','12:02','11:58'], smallest difference = 4 minutes

3. input = ['22:00','00:30'], smallest difference = 150 minutes

In case 1, given the two values in the input sequence, the smallest difference is the number of minutes between the two clock time values, which is 25 minutes.

In case 2, given the three values in the input, the smallest difference is the number of minutes between values '11:58' and '12:02'.

In case 3, one needs to consider there are two ways to count the difference between two time values, in the clockwise and anti-clockwise direction. Going clockwise, the difference is 150 minutes, while going anti-clockwise, the difference is 1290 minutes. As the problem statement is about finding the smallest difference, the smaller value should be considered when computing the difference.

Your task is to implement the details of the smallest_minute_difference function to determine the smallest difference between any two values in the provided list of input values. The algorithm is expected to return a number indicating the smallest difference, considering minutes as the unit of measurement. In the above cases, the function is expected to return 25, 4 and 150 respectively. The difference is expected to be a positive number, i.e. it is treated as an absolute value. The difference can be zero, if two similar time values are present in the input.

The code that I've written:

import time
from datetime import datetime
def minimum_time_difference(timeInstants):
  timeInstants=sorted((time.strptime(d, "%H:%M") for d in timeInstants))
    fmt = '%H:%M'
    timeInstants=sorted(timeInstants)
    diff = '24:59' #I need to assign a very big value here
    diff = datetime.strptime(diff, fmt)

    n=len(timeInstants)
    for i in range(n):
        timeInstants[i] = datetime.strptime(timeInstants[i], fmt)
    for i in range(n): 
        print(timeInstants[i])
        if timeInstants[i+1] - timeInstants[i] < diff: 
            diff = timeInstants[i+1] - timeInstants[i] 

    print(diff)
    return diff   

def main():
  timeInstants = ['11:00','12:02','11:58']
  minimum_value = minimum_time_difference(timeInstants)
  message = 'Given time instant values {0}, minimum difference between any two time instants is {1}\n'.format(
      timeInstants, minimum_value)
  print(message)


if __name__ == '__main__':
  main()

The code that I have written is giving me the error:

TypeError: unorderable types: datetime.timedelta() < datetime.datetime

What am I doing wrong and is my approach correct?

Answer 1

You can create the itertools.product of all your times by themselfs (thats combining each time with each other including itself). Then calculate the difference between these time pairs and take the smallest that is bigger then 0 (because self-self pairings). This way you only ever compare timedeltas (or you simply get the minimal timedelta) - you do not compare times with timedeltas.

import datetime
from datetime import datetime, timedelta
from itertools import product

def minimum_time_difference(timeInstants):
    # same time twice in list: set is shorter then list: return 0 
    if len(timeInstants) != len(set(timeInstants)):
        return 0
    # convert to datetime
    timeInstants = set(datetime.strptime(d, "%H:%M") for d in timeInstants)
    # convert to timedeltas from pairs
    diffs = set(abs(a-b ) for a,b in product(timeInstants, timeInstants))
    diffs |= set(abs(a-(b+timedelta(days=1))) for a,b in product(
                                                               timeInstants, timeInstants))
    print(diffs)
    # remove 0 times
    m = min(d for d in diffs if d)
    return m 


times = [ '00:00','23:59']
minimum_value = minimum_time_difference(times)
print(minimum_value)

Output:

{datetime.timedelta(0), datetime.timedelta(1, 86340), datetime.timedelta(0, 60), 
 datetime.timedelta(1), datetime.timedelta(0, 86340)}

0:01:00  # 1 minutes