Meeting Room ii: DSA

Let’s see the problem statement

Description

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example

Example1

Input: intervals = [(0,30),(5,10),(15,20)]
Output: 2
Explanation:
We need two meeting rooms
room1: (0,30)
room2: (5,10),(15,20)

Example2

Input: intervals = [(2,7)]
Output: 1
Explanation: 
Only need one meeting room

Approach 1:

A naive approach of solving the problem is , with a time complexity of o(n²).The key idea is first sort the interval-list provided , which takes a time complexity of o(nlgn), then iterate through the entire array and then on finding an item check whether any conference room already allocated, is able to be deallocated before start time of this item , if yes , replace the end time of that already allocated conference, by this end time of this new item, as this is the conference meeting that is currently going to be organized at that room where the old conference had been conducted, if no such room is available then , allocate a new room by incrementing a counter variable

The time complexity would be o(n²)

Space complexity would be o(1)

Approach 2:

On analyzing the problem we find that, whatsoever the case, for a meeting to be conducted a room is to be allocated. So one of the optimized solution is to iterate through the interval list , and for each item in the same, create a list of tuples , where each tuple is (start_time , 1), or (end_time,-1) fashion, that is upon starting a conference a room is allocated , indicated by the +1 and upon ending the meeting a room need to be deallocated , that is -1 , this takes o(n) time. Then we sort the items in this newly created list based on the timings.

Then iterates through the list goes on adding the second item of each tuple, which is -1 or +1 , this means that at any time the maximum sum formed by this item , +1 or -1 will be the , minimum number of rooms required.

Time complexity : o(nlgn)

Space complexity : o(n)

Solution:

The solution is given below

Approach 3

Third approach is based on the heap data structure . Sort the intervals based on the start time, Then the min heap holds the end time of each of the scheduled meeting. If a current meeting to be conducted has the start time greater than the minimum among the end times in the heap then that meeting is popped, and the end time of this new meeting is pushed and heap is heapified. If the current meeting to be scheduled has the start time , which is greater than the least end time of the already scheduled meeting, then a new room to be assigned in to the heap. At any instant, the minimum rooms required will be maximum number of nodes contained in the heap.

Space: O(n)

Time :soring intervals + push to the heap ans sort[(lgn ) time the number of nodes inserted.]

total =O(nlgn)