trucks.py

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