arrays - 给定列车时刻表所需的最少站台数量

Question

给定到达火车站的所有火车的到达和出发时间，找到火车站所需的最少站台数量，以便没有火车等待。我们有两个数组，分别代表停靠的火车的到达和离开时间。

例子:

输入1:

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

输出 1: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 之间)

我可以从 geeksforgeeks 找到 O(nLogn) 复杂度的解决方案，我们可以在 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++;
    }
}