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

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.

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

		           conferenceRoom++;

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

}

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

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…

U r may be wrong…
ur code :
B0ZZOw - Online C++0x Compiler & Debugging Tool - Ideone.com

Please see the edited code.

yeap…But How to solve this using greedy???

Please , write code in c++…@vinogeetha