Skip to content

Instantly share code, notes, and snippets.

@rvprasad

rvprasad/overlapping_intervals.py

Created November 6, 2018 03:50
Show Gist options
  • Save rvprasad/632a9befc6ca9cd2e7121ac8c7839c7a to your computer and use it in GitHub Desktop.
Save rvprasad/632a9befc6ca9cd2e7121ac8c7839c7a to your computer and use it in GitHub Desktop.
Download ZIP
Calculate the maximum number of overlapping intervals
Raw
overlapping_intervals.py
# Given a list of intervals, calculate the maximum number of overlapping intervals.
# Each interval is inclusive at both ends.
def solve(intervals): # list of pairs
tmp1 = set(y for x in intervals for y in x)
tmp2 = max(map(lambda x: sum(1 if y[0] <= x <= y[1] else 0 for y in intervals), tmp1))
print "%s %d" % (intervals, tmp2)
solve([(1,5), (2,4), (3, 6)])
solve([(1,5), (2,3), (4, 6), (7,9)])
solve([(1,5), (6,10), (11, 16), (17,19)])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment