Skip to content

Instantly share code, notes, and snippets.

@boompig
Last active November 24, 2015 16:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save boompig/e133910e8925a70f5b32 to your computer and use it in GitHub Desktop.
Save boompig/e133910e8925a70f5b32 to your computer and use it in GitHub Desktop.
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