171_Amazon_Find_Busiest_Period.py

"""
This problem was asked by Amazon.

You are given a list of data entries that represent entries and exits of groups of people into a building.
An entry looks like this:

{"timestamp": 1526579928, count: 3, "type": "enter"}

This means 3 people entered the building. An exit looks like this:

{"timestamp": 1526580382, count: 2, "type": "exit"}

This means that 2 people exited the building. timestamp is in Unix time.

Find the busiest period in the building, that is, the time with the most people in the building.
Return it as a pair of (start, end) timestamps.
You can assume the building always starts off and ends up empty, i.e. with 0 people inside.
"""

def busiest_period(movement_list):
    building_states = [(None, None, 0)]

    for movement in movement_list:
        last_building_state = building_states[-1]
        if movement["type"] == "enter":
            if last_building_state[2] == 0:
                new_building_state = (movement["timestamp"], movement["timestamp"], last_building_state[2] + movement["count"])
            else:
                new_building_state = (last_building_state[0], movement["timestamp"], last_building_state[2]+movement["count"])
            building_states.append(new_building_state)
        else:
            # exit movement
            last_building_state = building_states[-1]
            new_building_state = (last_building_state[0], movement["timestamp"], last_building_state[2] - movement["count"])
            building_states.append(new_building_state)
    building_states.sort(key=lambda x: x[2],reverse=True)
    return building_states[0][0], building_states[0][1]


def busiest_period_2(movement_list):
    periods = (None, None)

    num_people, max_num_people = 0, 0

    # sort the entries by timestamp
    sorted_entries = sorted(movement_list, key=lambda e: e["timestamp"])

    for i, entry in enumerate(sorted_entries):
        if entry["type"] == "enter":
            num_people+=entry["count"]
        else:
            num_people-=entry["count"]

        if num_people > max_num_people:
            max_num_people = num_people
            periods = (entry["timestamp"], sorted_entries[i+1]["timestamp"])

    return periods
if __name__ == '__main__':
    building_movements = [
        {"timestamp": 1526579928, "count": 2, "type": "enter"},
        {"timestamp": 1526579938, "count": 2, "type": "exit"},
        {"timestamp": 1526579948, "count": 5, "type": "enter"},
        {"timestamp": 1526579958, "count": 7, "type": "enter"},
        {"timestamp": 1526579968, "count": 8, "type": "exit"},
        {"timestamp": 1526579988, "count": 10, "type": "enter"},
        {"timestamp": 1526579988, "count": 14, "type": "exit"}
    ]
    events = [
        {"timestamp": 1526579928, "count": 3, "type": "enter"},
        {"timestamp": 1526579982, "count": 4, "type": "enter"},
        {"timestamp": 1526580054, "count": 5, "type": "exit"},
        {"timestamp": 1526580128, "count": 1, "type": "enter"},
        {"timestamp": 1526580382, "count": 3, "type": "exit"}
    ]

    #
    print(busiest_period(building_movements))
    print(busiest_period_2(building_movements))


    print(busiest_period(events))
    print(busiest_period_2(events))