Factory Machines

A factory has n machines which can be used to make products. Your goal is to make a total of t products.

For each machine, you know the number of seconds it needs to make a single product. The machines can work simultaneously, and you can freely decide their schedule.

What is the shortest time needed to make t products?

Example:

Input:  n = 3, t = 7, arr = {3, 2, 5}
Output: 8

Approach

C++

#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;

bool check(long long mid, long long t,
           long long n, vector<long long> &arr)
{
    long long cnt = 0;
    for (long long i = 0; i < n; i++)
    {
        cnt += mid / arr[i];
        if (cnt >= t)
            return true;
    }
    return false;
}

long long factoryMachines(long long n, long long t,
                          vector<long long> &arr)
{

    long long low = 0, high = INF;
    while (low + 1 < high)
    {
        long long mid = (low + high) / 2;
        if (check(mid, t, n, arr))
            high = mid;
        else
            low = mid;
    }
    return high;
}

int main()
{

    long long n = 3, t = 7;

    vector<long long> arr = {3, 2, 5};

    cout << factoryMachines(n, t, arr) << "\n";

    return 0;
}