 # Interval Partitioning Problem

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;
}
``````

I have tested a lot. It’s 100% true. (I think…)

test1 : http://ideone.com/hCoeC6

test2 : http://ideone.com/pM0iPu

Please let me know if it’s failing on any test data.

1 Like

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]<=bigArray[i+index] && bigArray[i][index]>=bigArray[i+index])

``````		           conferenceRoom++;

alert("Conference room needed : "+ conferenceRoom);
``````

}

Tnq so much…@only4
Please tell - What logic of this problems???

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 : http://ideone.com/Dasz1D
It will be very helpful if u can simply implement that code…

U r may be wrong…
ur code :
http://ideone.com/B0ZZOw