CPU - Editorial

editorial
1

PROBLEM LINK:

Contest

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

DIFFICULTY:

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][0],1});
	v.push_back({intervals[i][1],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