This post is completed by 1 user

  • 0
 Add to List
Medium

521. Maximum overlaps in a given list of time intervals

Interval is defined as [start, end]- the start of the interval to the end of the interval. Given the list of Intervals write an algorithm to find the maximum number of intervals overlapping at any point in time.

Example:

Given Intervals: [[0,2], [3,7], [1,5], [7,8], [4,6]]
Maximum overlapping: 3
Explanation: Interval (4, 5) is overlapping 3 given intervals [3,7], [1,5], [4,6]

Given Intervals: [[0,5], [6,8], [1,7]]
Maximum overlapping: 2

Given Intervals: [[0,2], [3,7], [7,8]]
Maximum overlapping: 1

Approach:

  • Create a list and insert all the interval times (both start and end) along with the marker to identify whether the time is start time or end time.
  • Sort the list in ascending order of times.
  • Initialize counter = 0, maxOverlap = 0.
  • Iterate the list from left to right. For each time-
    • If time is start-time - do counter++.
    • If time is end-time - do counter--.
    • Check if counter > maxOverlap, do maxOverlap = counter.
  • Return maxOverlap.

Time Complexity: O(nlogn)

 

Output: 

Given Intervals: [[0,2], [3,7], [1,5], [7,8], [4,6]]
Maximum overlapping: 3

Related Problems: