intervals_queue.py

import heapq
from collections import deque

def insert_into_queue(item, queue):
    if not item.is_empty():
        queue.push(item)


class Queue(object):
    def __init__(self, fn):
        self.key_fn = fn
        self.heap = []

    def push(self, item):
        key = self.key_fn(item)
        heapq.heappush(self.heap, (key, item))

    def pop(self):
        key, item = heapq.heappop(self.heap)
        return item

    def __len__(self):
        return len(self.heap)


def get_over_limit_queue(interval_list, limit):
    queue = Queue(lambda interval: interval.start)
    for interval in interval_list:
        insert_into_queue(interval, queue)
    done = deque()
    while len(queue) >= 2:
        a = queue.pop()
        b = queue.pop()
        if a.intersects_with(b):
            overlap = a.get_intersection(b)
            if overlap is not None:
                insert_into_queue(overlap, queue)
                insert_into_queue(b, queue)
                done.append(a)
            else:
                insert_into_queue(a)
                insert_into_queue(b)
        else:
            done.append(a)
            queue.push(b)
    if len(queue) == 1:
        a = queue.pop()
        done.append(a)
    for interval in done:
        if interval.val > limit:
            return True
    return False