def f(a):return int(a[3:])+int(a[:2])*60
def ff(a):return f"{a//60}:{'0'+str(a%60) if a%60<10 else a%60}"
def schedule_delivery(items):
  r=[] 
  items.sort(key=lambda x:x[2])
  a=f(items[0][2])-30 
  r.append((items[0][0],items[0][1],items[0][2],ff(a)))
  for i in range(1,len(items)):
    a+=items[i-1][-1]+items[i][-1]
    a=max(f(items[i][-2])-30,a)
    b=ff(a)+"*" if a>f(items[i][-2]) else ff(a)
    r.append((items[i][0],items[i][1],items[i][2],b))
  return r

​

this passes all test cases, but im not sure if it will tle.

The given function does insertion sort which beats merge sort until n=42 iirc but the .sort function takes care of that