A plane journey

A flight company has to schedule a journey of $N$ groups of people from the same source to the same destination. Here, $A_1,A_2,...,A_N$ represents the number of people in each group. All groups are present at the source. The flight company has $M$ planes where $B_1,B_2,...,B_m$ represents the capacity of each plane.

You are required to send all groups to destination with the following conditions:

1. Each plane can travel from the Source to Destination with only one group at a time such that capacity of a plane is enough to accommodate all people in that group.
2. All people belonging to the same group travel together.
3. Every plane can make multiple journeys between source and destination.
4. It costs 1 unit of time to travel between source to destination and vice versa.

Example:

Input: n = 4, m = 3, a = {2, 1, 2, 6}, b = {5, 5, 6}
Output: 3

Approach

Java

public class PlaneJourney {
    public static void main(String[] args) {
        int n = 4;
        int m = 3;
        int[] a = { 2, 1, 2, 6 };
        int[] b = { 5, 5, 6 };

        a = radixSort(a);
        b = radixSort(b);
        if (a[n - 1] > b[m - 1]) {
            System.out.println(-1);
            return;
        }
        int ans = 0;
        for (int i = 0; i < n;) {
            int j = upperBound(b, a[i]);
            while (i < n && j < m) {
                if (j >= 0 && a[i] <= b[j])
                    i++;
                j++;
            }
            if (i == n)
                ans++;
            else
                ans += 2;
        }
        System.out.println(ans);
    }

    public static int upperBound(int[] a, int v) {
        return upperBound(a, 0, a.length, v);
    }

    public static int upperBound(int[] a, int l, int r, int v) {
        int low = l - 1, high = r;
        while (high - low > 1) {
            int h = high + low >>> 1;
            if (a[h] <= v) {
                low = h;
            } else {
                high = h;
            }
        }
        return low;
    }

    public static int[] radixSort(int[] f) {
        int[] to = new int[f.length];
        {
            int[] b = new int[65537];
            for (int i = 0; i < f.length; i++)
                b[1 + (f[i] & 0xffff)]++;
            for (int i = 1; i <= 65536; i++)
                b[i] += b[i - 1];
            for (int i = 0; i < f.length; i++)
                to[b[f[i] & 0xffff]++] = f[i];
            int[] d = f;
            f = to;
            to = d;
        }
        {
            int[] b = new int[65537];
            for (int i = 0; i < f.length; i++)
                b[1 + (f[i] >>> 16)]++;
            for (int i = 1; i <= 65536; i++)
                b[i] += b[i - 1];
            for (int i = 0; i < f.length; i++)
                to[b[f[i] >>> 16]++] = f[i];
            int[] d = f;
            f = to;
            to = d;
        }
        return f;

    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int planeJouney(int n, int m, vector<int> a, vector<int> b)
{

    //sort both arrays in reverse order
    sort(b.begin(), b.end(), greater<int>());
    sort(a.begin(), a.end(), greater<int>());

    //if first element of first array is
    //large then return -1
    if (b[0] < a[0])
    {
        return -1;
    }
    else
    {
        int i = 1;
        int j = 1;
        int time = 1;
        int source = m - 1;
        int destination = 1;
        int maxtime = -1;

        while (i < n)
        {
            while (b[j] < a[i])
            {
                i++;
                time += 2;

                if (time > maxtime)
                    maxtime = time;
            }
            j++;
            i++;
            time = 1;
            if (time > maxtime)
                maxtime = time;

            source--;
            destination++;
            if (j == m && i != n)
            {
                if (source >= (n - i))
                {

                    maxtime++;
                    break;
                }
                else
                {
                    source = m;
                    maxtime++;
                    if (source >= n - i)
                    {
                        maxtime++;
                        break;
                    }
                    else
                    {
                        int k = ((n - i) / source) + 
                          ((n - i) % source != 0);
                        maxtime += 2 * k - 1;
                    }
                }
            }
        }

        if (time > maxtime)
            maxtime = time;
        return maxtime;
    }
}
int main()
{
    int n = 4, m = 3;

    vector<int> a = {2, 1, 2, 6};
    vector<int> b = {5, 5, 6};

    cout << planeJouney(n, m, a, b) << "\n";
    return 0;
}