Minimum time

help
1

we have y units of work and want to find out the minimum time required to finish the work

you will be given the sorted array arr[] where arr[i] denotes the time taken by ith person to do 1 unit of work
we have to find minimum time to fiish the work

4(total units of work)
3(total no of user)
1 1 2(0th person takes 1 second ,1st person takes 1 second,2nd person takes 2 seconds)

output
2

explanation
here if we allocate 1 unit of work to 0th person and 1st user at start then after 1 second 2 units of work will be completed again after 1 second if we allocate 1 unit of work to 0th and 1st person 2 units of work will be completed

so total 4 units in 2 seconds
so answer is 2

pls share approach
array is already sorted
this was asked in squad coding round on campus

@guitarlover @ssrivastava990 @anon55659401 @deeepeshthakur
pls help

1 Like
2

Constraints?

3

total time t<=50
no of user<=20

@deeepeshthakur

4

You could do this naively. Make an array which stores the time taken by each user individually. and initial time is set to 0. Now assign the next unit of work to the user whose individual time after the work-assignment is minimum.

I hope this was helpful.

5

can u give an example @deeepeshthakur

6 
#include<bits/stdc++.h>
#define iint int
#define pll std::pair<iint,iint>
#define rep(i,a,b) for(iint i=(iint)a;i<(iint)b;i++)
#define per(i,a,b) for(iint i=(iint)a;i>(iint)b;i--)
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define full(a) a.begin(),a.end()
#define rfull(a) a.rbegin(),a.rend()

using namespace std;
const double pi=acos(-1.0);
const double pii=2*pi;
const double eps=1e-6;
const long long MOD=1e9+7;

void solve(){
	int work, users;
	std::cin >> work >> users;
	std::vector<int> a(users,0),time_taken(users,0);

	for(int i=0;i<users;i++)
		std::cin >> a[i];
	int ans = 0;
	for(int i=0;i<work;i++){
		int curr_min = int(1e9), ind = 0;
		for(int j=0;j<users;j++){
			if(time_taken[j]+a[j] < curr_min){
				curr_min = time_taken[j]+a[j];
				ind = j;
			}
		}
		time_taken[ind]=curr_min;
		ans = std::max(ans,time_taken[ind]);
	}
	std::cout << ans << "\n";
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	// int t;
	// std::cin >> t;
	// while(t--){
	// 	solve();
	// }

	solve();
	return 0;
}
7

curr_min=time_taken[j]+a[j] :slight_smile:

1 Like
8

Oh Sorry! Thanks @choudhary463