Given an array of meeting time intervals consisting of start and end times i.e [[0, 30],[5, 10],[15, 20]].
How to find the minimum number of conference rooms required without priority queue?
Output : 2
Given an array of meeting time intervals consisting of start and end times i.e [[0, 30],[5, 10],[15, 20]].
How to find the minimum number of conference rooms required without priority queue?
Output : 2
I have written a code based on your question.
NEW EDIT: Re-written
#include<bits/stdc++.h>
using namespace std;
int roomsneeded(vector< int > start, vector< int > over, int n)
{
sort(start.begin(), start.end());
sort(over.begin(), over.end());
int rooms_needed = 1, result = 1;
int i = 1, j = 0;
while (i < n && j < n)
{
if (start[i] < over[j])
{
rooms_needed++;
i++;
if (rooms_needed > result)
result = rooms_needed;
}
else
{
rooms_needed--;
j++;
}
}
return result;
}
int main()
{
vector< int > start,over;
int noofconf,starttime,endtime;
cin>>noofconf;
for(int i = 0 ; i < noofconf ; i++)
{
cin>>starttime>>endtime;
start.push_back(starttime);
over.push_back(endtime);
}
cout << roomsneeded(start, over, noofconf);
return 0;
}
Some help from :- Minimum Number of Platforms Required for a Railway/Bus Station - GeeksforGeeks
I have tested a lot. It’s 100% true. (I think…)
test1 : hCoeC6 - Online C++0x Compiler & Debugging Tool - Ideone.com
test2 : pM0iPu - Online C++0x Compiler & Debugging Tool - Ideone.com
Please let me know if it’s failing on any test data.
I have tried in Js.Below is the script.
function result(){
var bigArray = [[0, 30],[5, 10],[15, 20]];
var conferenceRoom = 1; var index = 1;
for(i=0;i<bigArray.length-index;i++)
if(bigArray[i][0]<=bigArray[i+index][0] && bigArray[i][index]>=bigArray[i+index][0])
conferenceRoom++;
alert("Conference room needed : "+ conferenceRoom);
}
Your code may something wrong…because
Input :
3
1 3
2 4
3 5
Your code show output : 4
Corrected Output : 2
I have collected a code from internet…but could not understand…link : Dasz1D - Online C++0x Compiler & Debugging Tool - Ideone.com
It will be very helpful if u can simply implement that code…
Please see the edited code.
yeap…But How to solve this using greedy???