 # CPU - Editorial

Contest

Author: Sumukh Bhardwaj
Tester: Rahul Sharma
Editorialist: Sumukh Bhardwaj

EASY

# PREREQUISITES:

Basic Programming

# PROBLEM:

Given an array of time intervals `intervals`, where `intervals[i] = [starti, endi]`, return the minimum number of CPUs as per the question statement.

# QUICK EXPLANATION:

Sort the intervals according to their starting/ending time, if a starting time comes increment the number of processors if an ending time comes decrement the number of processors.

# EXPLANATION:

For each interval [start_i, end_i] break it into two parts [start_i, 1] and [end_i, 0]. Now sort these in ascending order. Traverse the sorted pairs if a pair comes with value 1 as the second value in pair that means a process needs to start hence increment the number of processors else if the pair comes with value 0 in the second value then that means a processor is released hence decrement the processor count. After each such operation finds the maximum of processor count.

# COMPLEXITIES

Here N is the number of processes.

TIme Complexity: O(NLogn). For sorting

Space Complexity: O(N). For storing 2*N pairs.

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>
using namespace std;

int minMeetingRooms(vector<vector<int>>& intervals) {

int i,cnt=0,ans=0,n = intervals.size();

vector<pair<int,int>>v;

for(i=0;i<n;i++)
{
v.push_back({intervals[i],1});
v.push_back({intervals[i],0});
}

sort(v.begin(),v.end());

for(i=0;i<v.size();i++)
{
if(v[i].second==1)
cnt++;
else
cnt--;

ans= max(ans,cnt);
}

return ans;
}

int main() {
ios_base::sync_with_stdio(false);

int n,x,i, y, t;

cin>>t;
while(t--)
{
cin>>n;
vector<vector<int>>v;

for(i=0;i<n;i++)
{
cin>>x>>y;
v.push_back({x, y});
}
cout<<minMeetingRooms(v)<<endl;
}

return 0;
}
``````
1 Like