Skip to content

Instantly share code, notes, and snippets.

@omokehinde
Last active November 7, 2022 17:25
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save omokehinde/80ed283556f3957562053318c4702d80 to your computer and use it in GitHub Desktop.
Save omokehinde/80ed283556f3957562053318c4702d80 to your computer and use it in GitHub Desktop.
Find minimum laptop a school needs to rent out to students
# you're given a list of time intervals during which students at a school need a laptop.
# These time intervals are represented by pairs of integers [start, end], where 0 <= start < end.
# However, start and end don't represent real times; therefore, they may be greater than 24.
# No two students can use a laptop at the same time, but immediately after a student is done
# using a laptop, another student can use that same laptop. For example, if one student rents a
# laptop during the time interval [0, 2], another student can rent the same laptop during any
# time interval starting with 2. Write a function that returns the minimum number of laptops
# that the school needs to rent such that all students will always have access to a laptop when
# they need one. laptopRentals(times)
# Parameters times: Array (of Array (of Integers)) - A 2D array containing the times the
# student would require a laptop.
# Return Value Integer - Minimum number of laptops the school needs to rent.
# Examples times Return Value
# [[0,2],[1,4],[4,6],[0,4],[7,8],[9,11],[3,10]] 3
# [[0,4],[2,3],[2,3],[2,3]] 4
# [[1,5],[5,6],[6,7],[7,9]] 1
def laptopRentals(times):
events = []
times.sort()
for t in times:
events.append(('start',t[0]))
events.append(('end',t[1]))
events.sort(key=lambda x: x[1])
laptops_in_use = 0
max_in_use = 0
for event in events:
if event[0] == 'start':
laptops_in_use += 1
max_in_use = max(max_in_use, laptops_in_use)
if event[0] == 'end':
laptops_in_use -= 1
return max_in_use
print(laptop_rentals([[0,2],[1,4],[4,6],[0,4],[7,8],[9,11],
[3,10]]))
@omokehinde
Copy link
Author

Is this 2N?

@omokehinde
Copy link
Author

times need to be sorted first to ensure algorithm works correctly.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment