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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment