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

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

Примеры:

Вход1:

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

Выход1: 3

Одновременно ходит не более трех поездов (между 11:00 и 11:28).

Вход2:

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

Выход2: 2

Одновременно ходит не более двух поездов (между 23:00 и 200)

Вход3:

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

Выход3: 3

Не более трех поездов одновременно (от 0 до 300)

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

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

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


arrays algorithm data-structures greedy
person Rahul Chauhan    schedule 21.05.2018    source источник
comment
Возможный дубликат Учитывая набор интервалов, как найти среди них максимальное количество пересечений,   -  person n. 1.8e9-where's-my-share m.    schedule 21.05.2018
comment
Это может быть похоже на решение проблемы, но обе проблемы разные: здесь указан диапазон расписаний от 0 до 24:00, а также расписание отправления поезда может быть на следующий день, что означает, что время отправления может быть меньше, чем время прибытия, например. прибытие 2300 и отправление 200. Можно предположить, что ни один поезд не будет стоять на платформе более 24 часов.   -  person Rahul Chauhan    schedule 21.05.2018
comment
Нет однозначного ответа, возможен ли опрокидывание и вы не знаете, когда какой поезд прибывает и когда отправляется. Например, прибытия={0010,2340}, отправления={0020,2350} могут быть (поезд 1 прибывает в 00:10, отправляется в 00:20, поезд 2 прибывает в 23:40, отправляется в 23:50) или (поезд 1 прибывает в 23:40, отправляется в 00:20, поезд 2 прибывает в 00:10, отправляется в 23:50). Вы не можете ограничить время остановки, например, 12 часов или даже 1 час, потому что возможна точно такая же ситуация, только с большим количеством поездов.   -  person n. 1.8e9-where's-my-share m.    schedule 21.05.2018
comment
Каждое значение индекса представляет собой конкретный поезд, например. 0-й индекс представляет поезд 1, 1-й индекс представляет поезд 2. В данном примере прибытия = {0010,2340}, отправления = {0020,2350}, перекрытия нет. Для поезда 1 -> индекс 0 прибытие/отправление - 0010/0020 --------- Для поезда 2 -> индекс 1 прибытие/отправление - 2340/2350   -  person Rahul Chauhan    schedule 21.05.2018
comment
Тогда вы не сможете сделать это за O(n), потому что вам нужно отсортировать данные. Вы можете выполнить сортировку по основанию или ведру, потому что у вас есть только числа от 0 до 2359, но это своего рода мошенничество.   -  person n. 1.8e9-where's-my-share m.    schedule 21.05.2018
comment
Мы можем сделать это за O(n). Я работаю над решением, которое опубликую после тщательного тестирования.   -  person Rahul Chauhan    schedule 21.05.2018
comment
@н.м. Надеюсь, теперь вы поняли эту проблему, можете ли вы решить этой задачи за O(n), и вы все еще думаете, что это дубликат того.   -  person Rahul Chauhan    schedule 21.05.2018
comment
Решение задачи на основе набора входных данных не является мошенничеством. Если я поставлю перед вами задачу, чтобы система голосования выбрала победителя из всех кандидатов, будете ли вы по-прежнему использовать быструю сортировку или любую другую сортировку, которая дала вам O(nlogn) ?? или вы будете использовать сортировку подсчетом.   -  person Rahul Chauhan    schedule 21.05.2018
comment
Это решение не обобщает. Если время задано с произвольной точностью, а не с 1 минутой, вы вдруг обнаружите, что ваш метод работает несколько хуже. В реальной жизни я бы определенно использовал быструю сортировку большую часть времени, потому что теоретические преимущества методов, не основанных на сравнении, на практике не имеют значения. Если мне нужно отправить домашнее задание по CS101, я, конечно, буду использовать все, что требует сложности.   -  person n. 1.8e9-where's-my-share m.    schedule 21.05.2018

Ответы (1)


arrow_upward
3
arrow_downward

Поскольку у нас есть время прибытия и время отправления от 1 до 2400 или от 0 до 2399, мы можем сортировать временной интервал с помощью сортировки Redix, поскольку нам нужно использовать сортировку подсчетом только четыре раза, поэтому сложность сортировки прибытия и отправления будет 4 * 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++;
    }
}

}

person Rahul Chauhan    schedule 21.05.2018