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

给定到达火车站的所有列车的到达和离开时间，找出火车站所需的最少站台数，以便列车不等待我们得到了两个数组，表示停站列车的到达和离开时间。
示例：
输入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之间）
我可以从GoeksFrEGEKS中找到一个O（nLogn）复杂度的解决方案，我们能用O（n）时间复杂度来解决吗？
列车时刻表的范围固定在0到2399之间，并且列车发车时刻表可以是第二天，这意味着发车时间可以小于到达时间，例如到达2300和离开200。
我们可以假设没有一列火车在站台上停留超过24小时。

最佳答案

由于到达时间和出发时间在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++;
    }
}

}