max_surgeries.py

from functools import cmp_to_key

class SurgeryEvent(object):
    TYPE_START = 'surger_start'
    TYPE_END = 'surgery_end'

    def __init__(self, time, type):
        self.time = time
        self.type = type

    @classmethod
    def start_and_end_events(cls, surgery):
        if not surgery:
            return []

        return [
            SurgeryEvent(time=surgery['start'], type=SurgeryEvent.TYPE_START),
            SurgeryEvent(time=surgery['end'], type=SurgeryEvent.TYPE_END)
        ]

    @classmethod
    def get_events(cls, surgeries):
        if not surgeries:
            return []

        events = []
        for surgery in surgeries:
            events.extend(SurgeryEvent.start_and_end_events(surgery))
        return events

    def __str__(self):
        return '<Event time:' + str(self.time) + 'type:' + self.type + '>'


def _cmp_surgery_events(e1, e2):
    """
    Sort events based on time, if events the same time, move the event ends
    first, and the starts later
    We do that as same end time and start times is not considered an overlap
    While calculating max_concurrent surgeries, we want to remove a surgery
    which is ending, before adding a surgery that is starting
    """
    if e1.time > e2.time:
        return 1
    elif e1.time < e2.time:
        return -1
    else:
        if e1.type == SurgeryEvent.TYPE_START and e2.type == SurgeryEvent.TYPE_END:
            return 1
        elif e1.type == SurgeryEvent.TYPE_END and e2.type == SurgeryEvent.TYPE_START:
            return -1
    return 0


def find_max_num_concurrent_surgeries(surgeries):
    """
    Assumes all surgeries have end time greater than start time
    """
    events = SurgeryEvent.get_events(surgeries)

    events.sort(key=cmp_to_key(_cmp_surgery_events))

    max_concurrent_surgeries = 0

    current_max = 0
    for event in events:
        if event.type == SurgeryEvent.TYPE_START:
            current_max += 1
        if event.type == SurgeryEvent.TYPE_END:
            current_max -= 1

        if current_max > max_concurrent_surgeries:
            max_concurrent_surgeries = current_max

    print 'max number of surgeries possible', max_concurrent_surgeries
    return max_concurrent_surgeries



MAX_NUM_SURGERIES = 'max_num_surgeries'
SURGERIES = 'SURGERIES'
START = 'start'
END = 'end'

surgeries_and_outcomes = [
    {
        MAX_NUM_SURGERIES: 0,
        SURGERIES: [],
    }, {
        MAX_NUM_SURGERIES: 0,
        SURGERIES: None,
    }, {
        MAX_NUM_SURGERIES: 1,
        SURGERIES: [
            {START: 1, END: 3}
        ],
    }, {
        MAX_NUM_SURGERIES: 0,
        SURGERIES: [
            {START: 1, END: 1}
        ],
    }, {
        MAX_NUM_SURGERIES: 1,
        SURGERIES: [
            {START: 1, END: 1.1}
        ],
    }, {
        MAX_NUM_SURGERIES: 4,
        SURGERIES: [
            {START: 1, END: 2},
            {START: 1, END: 3},
            {START: 2, END: 5},
            {START: 2, END: 6},
            {START: 4, END: 5},
            {START: 4.5, END: 6},
        ],
    }, {
        MAX_NUM_SURGERIES: 2,
        SURGERIES: [
            {START: 1, END: 3},
            {START: 2, END: 3},
        ],
    }, {
        MAX_NUM_SURGERIES: 4,
        SURGERIES: [
            {START: 1, END: 5},
            {START: 3, END: 9},
            {START: 7, END: 13},
            {START: 11, END: 15},
            {START: 11, END: 17},
            {START: 16, END: 18},
            {START: 16, END: 19},
            {START: 16, END: 20},
        ],
    }, {
        MAX_NUM_SURGERIES: 4,
        SURGERIES: [
            {START: 1, END: 5},
            {START: 3, END: 9},
            {START: 7, END: 13},
            {START: 11, END: 15},
            {START: 11, END: 17},
            {START: 16, END: 18},
            {START: 16, END: 19},
            {START: 16, END: 20},
        ],
    }, {
        MAX_NUM_SURGERIES: 1,  # one, because, the start and end times overlap
        SURGERIES: [
            {START: 2, END: 4},
            {START: 1, END: 2},
        ],
    }

]

for s in surgeries_and_outcomes:

    max_num_surgeries = find_max_num_concurrent_surgeries(s[SURGERIES])
    assert max_num_surgeries == s[MAX_NUM_SURGERIES]