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)

 



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

Related Problems: