минимальное количество платформ, необходимое с учетом расписаний поездов

Question

Учитывая время прибытия и отправления всех поездов, которые достигают железнодорожной станции, найдите минимальное количество платформ, необходимых для железнодорожной станции, чтобы не ждать поезда.Нам даны два массива, которые представляют время прибытия и отправления поездов, которые останавливаются.

Примеры:

Input1:

arr[] = {904, 946, 952, 1100, 1508, 1806} dep[] = {915, 1202, 1128, 1135, 1900, 2001}

Output1: 3

Одновременно может быть не более трех поездов (между 1100 и 1128)

Вход 2:

arr[] = {2200, 2300} dep[] = {200, 300}

Выход 2: 2

Одновременно может быть не более двух поездов (от 2300 до 200)

Вход 3:

arr[] = {2200, 2300, 0,} dep[] = {300, 300, 300}

Выход 3: 3

Одновременно может быть не более трех поездов (от 0 до 300)

Я могу найти решение по сложности O (nLogn) от geeksforgeeks, можем ли мы решить его за O (n) сложности времени?

Диапазон расписаний здесь фиксирован от 0 до 2399, а также расписание отправления поездов может быть на следующий день, что означает, что время отправления может быть меньше времени прибытия, например, прибытие 2300 и отправление 200.

МыМожно предположить, что ни один поезд не остановится более чем на 24 часа на платформе.

Answer 1

Поскольку у нас есть время прибытия и время отправления от 1 до 2400 или от 0 до 2399, мы можем отсортировать интервал времени, используя сортировку Redix, поскольку только четыре раза нам нужно использовать сортировку отсчета, поэтому сложность сортировки прибытия и отправления будет 4 *n -> O (n).И тогда мы можем использовать слияние двух отсортированных массивов, чтобы найти перекрытие.который будет стоить n + n -> O (n).Таким образом, временная сложность решения этой проблемы составляет O (n).

public class MinimumRequiredPlatform {

public static void main(String args[]){
    Integer[] a1 = {2200, 2300};
    Integer[] b1 = {200, 300};
    int count = findMinRequiredPlatform(a1, b1);
    Assert.isTrue(count == 2, "expected 2 but found " + count);

    Integer a2[] = {904, 946, 952, 1100, 1508, 1806};
    Integer b2[] = {915, 1202, 1128, 1135, 1900, 2001};
    count = findMinRequiredPlatform(a2, b2);
    Assert.isTrue(count == 3, "expected 3 but found " + count);

    Integer[] a3 = {2200, 2300};
    Integer[] b3 = {2300, 300};
    count = findMinRequiredPlatform(a3, b3);
    Assert.isTrue(count == 2, "expected 2 but found " + count);

    Integer[] a4 = {2200, 2300, 0};
    Integer[] b4 = {300, 0, 300};
    count = findMinRequiredPlatform(a4, b4);
    Assert.isTrue(count == 3, "expected 3 but found " + count);
}


/**
 * Time complexity (4*n + 4*n) + (n+n) -> O(n), where n is the number of trains.
 * Space complexity O(n)
 */
private static int findMinRequiredPlatform(Integer[] arr, Integer[] dep) {
    int count = 0;

    int n = arr.length;

    List<Integer> l1 = new ArrayList<>(Arrays.asList(arr));
    List<Integer> l2 = new ArrayList<>(Arrays.asList(dep));

    for(int i = 0; i< n; i++){
        if (dep[i] < arr[i]) {
            l2.set(i, 2399);
            l1.add(0);
            l2.add(dep[i]);
        }
    }

    sort(l1);
    sort(l2);

    n = l1.size();
    int max = 0;
    int i = 0;
    int j = 0;
    while(i < n || j < n) {
        if(i >= n) {
            count--;
            j++;
        }
        else if (i<n && j< n) {
            if (l1.get(i) <= l2.get(j)){
                count++;
                i++;
            } else {
                count--;
                j++;
            }
        }

        if(count > max){
            max = count;
        }
    }

    return max;
}

// Time complexity 4*n -> O(n), space complexity O(n);
private static void sort(List<Integer> a) {
    Map<Integer, List<Integer>> map = new HashMap<>();
    int div = 1;
    int lastDiv;
    int count = 0;
    while(count < 4) {
        lastDiv = div;
        div *= 10;
        for (int i : a) {
            int v = (i % div)/lastDiv;
            if (map.containsKey(v)) {
                map.get(v).add(i);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(v, list);
            }
        }
        int ind = 0;
        for (int i = 0; i < 10; i++) {
            if (map.containsKey(i)) {
                List<Integer> l = map.remove(i);
                for (int v : l) {
                    a.set(ind, v);
                    ind++;
                }
            }
        }
        count++;
    }
}

}