This post is completed by 1 user
|
Add to List |
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)
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Main {
static class Interval {
int start;
int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public String toString() {
return "["+this.start+","+this.end+"]" ;
}
}
static class Time{
int time;
String type;
public Time(int time, String type) {
this.time = time;
this.type = type;
}
}
public static void maxOverlapIntervalCount(ArrayList<Interval> intervals){
System.out.println("Given Intervals: " + intervals.toString());
ArrayList<Time> allTimesList = new ArrayList<>();
for (int i = 0; i <intervals.size() ; i++) {
allTimesList.add(new Time(intervals.get(i).start, "start"));
allTimesList.add(new Time(intervals.get(i).end, "end"));
}
Collections.sort(allTimesList, new Comparator<Time>() {
@Override
public int compare(Time o1, Time o2) {
return o1.time-o2.time;
}
});
int maxOverlap = 0;
int count = 0;
for (int i = 0; i <allTimesList.size() ; i++) {
Time time = allTimesList.get(i);
if(time.type.equals("start"))
count++;
else
count--;
if(count>maxOverlap)
maxOverlap=count;
}
System.out.println("Maximum overlapping: " + maxOverlap);
}
public static void main(String[] args) {
ArrayList<Interval> intervals = new ArrayList<>();
intervals.add(new Interval(0,2));
intervals.add(new Interval(3,7));
intervals.add(new Interval(1,5));
intervals.add(new Interval(7,8));
intervals.add(new Interval(4,6));
maxOverlapIntervalCount(intervals);
}
}
class Interval:
def __init__(self, start, end):
self.start = start
self.end = end
def __str__(self):
return f"[{self.start},{self.end}]"
class Time:
def __init__(self, time, type):
self.time = time
self.type = type
def maxOverlapIntervalCount(intervals):
print("Given Intervals:", intervals)
allTimesList = []
for interval in intervals:
allTimesList.append(Time(interval.start, "start"))
allTimesList.append(Time(interval.end, "end"))
allTimesList.sort(key=lambda x: x.time)
maxOverlap = 0
count = 0
for time in allTimesList:
if time.type == "start":
count += 1
else:
count -= 1
maxOverlap = max(maxOverlap, count)
print("Maximum overlapping:", maxOverlap)
if __name__ == "__main__":
intervals = [
Interval(0, 2),
Interval(3, 7),
Interval(1, 5),
Interval(7, 8),
Interval(4, 6)
]
maxOverlapIntervalCount(intervals)
package main
import (
"fmt"
"sort"
)
type Interval struct {
start, end int
}
type Time struct {
time int
typ string
}
func maxOverlapIntervalCount(intervals []Interval) {
fmt.Print("Given Intervals: ", intervals)
fmt.Println("")
allTimesList := make([]Time, 0)
for _, interval := range intervals {
allTimesList = append(allTimesList, Time{interval.start, "start"})
allTimesList = append(allTimesList, Time{interval.end, "end"})
}
sort.Slice(allTimesList, func(i, j int) bool {
return allTimesList[i].time < allTimesList[j].time
})
maxOverlap := 0
count := 0
for _, time := range allTimesList {
if time.typ == "start" {
count++
} else {
count--
}
if count > maxOverlap {
maxOverlap = count
}
}
fmt.Print("Maximum overlapping: ", maxOverlap)
fmt.Println("")
}
func main() {
intervals := []Interval{
{0, 2},
{3, 7},
{1, 5},
{7, 8},
{4, 6},
}
maxOverlapIntervalCount(intervals)
}
Output:
Given Intervals: [[0,2], [3,7], [1,5], [7,8], [4,6]] Maximum overlapping: 3