educative.io

I think I have a better O(N) solution

Courses
,
#1 
def find_employee_free_time(schedule):
  if len(schedule) < 1:
    return []
  occupied = schedule[0]
  for k in range(1, len(schedule)):
    employee = schedule[k]
    i = 0
    j = 0
    while i < len(occupied) and j < len(employee):
      if employee[j].start < occupied[i].start:
        employee[j].start, employee[j].end, occupied[i].start, occupied[i].end = occupied[i].start, occupied[i].end, employee[j].start, employee[j].end
      elif employee[j].start <= occupied[i].end:
        occupied[i].end = max(occupied[i].end, employee[j].end)
        j += 1
      else:  # employee[j].start > occupied[i].end
        i += 1
    while j < len(employee):
      occupied.append(employee[j])
      j += 1
  result = []
  for i in range(1, len(occupied)):
    result.append(Interval(occupied[i-1].end, occupied[i].start))
  return result

If you don’t want to modify the schedule parameter, you can copy it to a temp structure, it still will be O(N). What do you think?

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5118951610646528

#2

Hi @Andres_Parra ,

It looks great :+1:.Thank you for sharing this.