Skip to content

Instantly share code, notes, and snippets.

@mkorpela
Last active August 29, 2015 14:10
Show Gist options
  • Save mkorpela/baf0df35a4220a96144b to your computer and use it in GitHub Desktop.
Save mkorpela/baf0df35a4220a96144b to your computer and use it in GitHub Desktop.
class TrucksAvailable(object):
def __init__(self):
self._trucks_available = []
def add_truck(self, times):
for start, end in times:
self._add_truck_to_time_slice(start, end)
def _add_truck_to_time_slice(self, start, end):
for time in range(start, end+1):
self._add_truck_to_time(time)
self._simplify()
def _simplify(self):
# NOT AT ALL OPTIMAL BUT DOES THE STUFF..
match_happened = True
while match_happened:
match_happened = False
for i in range(0, len(self._trucks_available)-1):
if (self._trucks_available[i][1]+1 == self._trucks_available[i+1][0] and
self._trucks_available[i][2] == self._trucks_available[i+1][2]):
self._trucks_available[i][1] = self._trucks_available[i+1][1]
self._trucks_available.pop(i+1)
match_happened = True
break
def _add_truck_to_time(self, time):
index = 0
to_insert = [[time, time, 1]]
for index, (start, end, count) in enumerate(self._trucks_available[:]):
if time <= end:
if time < start:
break
self._trucks_available.pop(index)
to_insert[0][2] = count + 1
if time < end:
to_insert.append([time+1, end, count])
if start < time:
to_insert.insert(0, [start, time-1, count])
break
index += 1
self._trucks_available = self._trucks_available[:index] + to_insert + self._trucks_available[index:]
def how_many_trucks_available(self, time):
return self._how_many_trucks_available(time, 0, len(self._trucks_available)-1)
def _how_many_trucks_available(self, time, low, high):
if high < low:
return 0
index = (low + high) / 2
start, end, trucks_available = self._trucks_available[index]
if start > time:
return self._how_many_trucks_available(time, low, index-1)
if time > end:
return self._how_many_trucks_available(time, index+1, high)
return trucks_available
if __name__ == '__main__':
T1 = [[1,4], [10, 12], [34, 57]]
T2 = [[3,5], [34, 35], [50, 56]]
T3 = [[10, 12]]
T4 = []
trucksAvailable = TrucksAvailable()
assert trucksAvailable.how_many_trucks_available(1) == 0
trucksAvailable.add_truck(T1)
print trucksAvailable._trucks_available
assert trucksAvailable.how_many_trucks_available(0) == 0
assert trucksAvailable.how_many_trucks_available(1) == 1
assert trucksAvailable.how_many_trucks_available(4) == 1
assert trucksAvailable.how_many_trucks_available(5) == 0
assert trucksAvailable.how_many_trucks_available(6) == 0
assert trucksAvailable.how_many_trucks_available(35) == 1
assert trucksAvailable.how_many_trucks_available(50) == 1
assert trucksAvailable.how_many_trucks_available(70) == 0
trucksAvailable.add_truck(T2)
print trucksAvailable._trucks_available
assert trucksAvailable.how_many_trucks_available(0) == 0
assert trucksAvailable.how_many_trucks_available(1) == 1
assert trucksAvailable.how_many_trucks_available(4) == 2
assert trucksAvailable.how_many_trucks_available(5) == 1
assert trucksAvailable.how_many_trucks_available(6) == 0
assert trucksAvailable.how_many_trucks_available(35) == 2
assert trucksAvailable.how_many_trucks_available(50) == 2
assert trucksAvailable.how_many_trucks_available(70) == 0
trucksAvailable.add_truck(T3)
print trucksAvailable._trucks_available
assert trucksAvailable.how_many_trucks_available(0) == 0
assert trucksAvailable.how_many_trucks_available(1) == 1
assert trucksAvailable.how_many_trucks_available(10) == 2
trucksAvailable.add_truck(T4)
print trucksAvailable._trucks_available
assert trucksAvailable.how_many_trucks_available(0) == 0
assert trucksAvailable.how_many_trucks_available(1) == 1
assert trucksAvailable.how_many_trucks_available(10) == 2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment