(A卷,100分)- 人数最多的站点（Java & JS & Python）

题目描述

公园园区提供小火车单向通行，从园区站点编号最小到最大通行如1~2~3~4~1，然后供员工在各个办公园区穿梭，通过对公司N个员工调研统计到每个员工的坐车区间，包含前后站点，请设计一个程序计算出小火车在哪个园区站点时人数最多。

输入描述

第1个行，为调研员工人数

第2行开始，为每个员工的上车站点和下车站点。
使用数字代替每个园区用空格分割，如3 5表示从第3个园区上车，在第5个园区下车

输出描述

人数最多时的园区站点编号，最多人数相同时返回编号最小的园区站点

用例

输入	3 1 3 2 4 1 4
输出	2
说明	无

题目解析

本题其实就是求解最大重叠区间个数的变种题。

即，我们只要找到具有最大重叠部分的区间的起点就是本题题解。

关于最大重叠区间个数求解，请看

上面视频的核心思想其实就是：

首先，将所有区间按开始位置升序
然后，遍历排序后区间，并将小顶堆中小于遍历区间起始位置的区间弹出（小顶堆实际存储区间结束位置），此操作后，小顶堆中剩余的区间个数，就是和当前遍历区间重叠数。

我们只需要在求解最大重叠数时，保留遍历的区间的起始位置即可。

对于JS而言，没有原生堆结构（即优先队列），因此我们需要手写小顶堆代码，关于优先队列，大家可以参考：

LeetCode – 1705 吃苹果的最大数目_伏城之外的博客-CSDN博客

但是本题是100分值的，可能不会存在大数量级，因此大家可以先尝试用有序数组代替小顶堆，如果不行，再实现小顶堆。

另外，本题和华为OD机试 – 最大化控制资源成本_伏城之外的博客-CSDN博客

很像，大家可以继续尝试做下上面这题。

2023.2.1根据网友指正，本题小火车是有可能走回程的，比如，坐车区间为 [3,2]，即从站点3 -> 站点4 -> 站点1 -> 站点2。

对于这种情况，就会破坏上面对于区间的排序。因此，我们需要将：该情况的坐车区间拆分为 [3, 4]和[1, 2]

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    n = lines[0] - 0;
  }

  if (n && lines.length === n + 1) {
    const ranges = lines.slice(1).map((line) => line.split(" ").map(Number));
    console.log(getResult(ranges));
    lines.length = 0;
  }
});

function getResult(ranges) {
  // 由于题目并未说有几个站点，因此需要计算出最后一个站点
  const last = Math.max.apply(null, ranges.toString().split(",").map(Number));

  // 如果存在 [3,2] 这种坐车区间，即从站点3 -> 站点4 -> 站点1 -> 站点2，则此时将该坐车区间拆分为 [3, 4]和[1, 2]
  const tmp = [];
  ranges.forEach((range) => {
    const [s, e] = range;

    if (s > e) {
      // 拆分
      tmp.push([s, last]);
      tmp.push([1, e]);
    } else {
      tmp.push(range);
    }
  });
  ranges = tmp;

  // 最大重叠区间个数求解
  ranges.sort((a, b) => a[0] - b[0]);
  const end = new PriorityQueue((a, b) => b - a);

  let max = 0;
  let ans = ranges[0][0];
  for (let range of ranges) {
    const [s, e] = range;

    while (end.size()) {
      const top = end.peek();

      if (top < s) {
        end.shift();
      } else {
        break;
      }
    }

    end.push(e);

    if (end.size() > max) {
      max = end.size();
      ans = s;
    }
  }

  return ans;
}

class PriorityQueue {
  constructor(cpr) {
    this.queue = [];
    this.cpr = cpr;
  }

  swap(a, b) {
    const tmp = this.queue[a];
    this.queue[a] = this.queue[b];
    this.queue[b] = tmp;
  }

  // 上浮
  swim() {
    let c = this.queue.length - 1;

    while (c >= 1) {
      const f = Math.floor((c - 1) / 2);

      if (this.cpr(this.queue[c], this.queue[f]) > 0) {
        this.swap(c, f);
        c = f;
      } else {
        break;
      }
    }
  }

  // 入队
  push(val) {
    this.queue.push(val);
    this.swim();
  }

  // 下沉
  sink() {
    let f = 0;

    while (true) {
      let c1 = 2 * f + 1;
      let c2 = c1 + 1;

      let c;
      let val1 = this.queue[c1];
      let val2 = this.queue[c2];
      if (val1 && val2) {
        c = this.cpr(val1, val2) > 0 ? c1 : c2;
      } else if (val1 && !val2) {
        c = c1;
      } else if (!val1 && val2) {
        c = c2;
      } else {
        break;
      }

      if (this.cpr(this.queue[c], this.queue[f]) > 0) {
        this.swap(c, f);
        f = c;
      } else {
        break;
      }
    }
  }

  // 出队
  shift() {
    this.swap(0, this.queue.length - 1);
    const res = this.queue.pop();
    this.sink();
    return res;
  }

  // 查看顶
  peek() {
    return this.queue[0];
  }

  size() {
    return this.queue.length;
  }
}

Java算法源码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[][] ranges = new int[n][2];

    for (int i = 0; i < n; i++) {
      ranges[i][0] = sc.nextInt();
      ranges[i][1] = sc.nextInt();
    }

    System.out.println(getResult(ranges));
  }

  public static int getResult(int[][] ranges) {
    // 由于题目并未说有几个站点，因此需要计算出最后一个站点
    Integer last =
        Arrays.stream(ranges)
            .map(range -> Math.max(range[0], range[1]))
            .max((a, b) -> a - b)
            .orElse(0);

    // 如果存在 [3,2] 这种坐车区间，即从站点3 -> 站点4 -> 站点1 -> 站点2，则此时将该坐车区间拆分为 [3, 4]和[1, 2]
    ArrayList<Integer[]> tmp = new ArrayList<>();
    for (int[] range : ranges) {
      int s = range[0];
      int e = range[1];

      if (s > e) {
        tmp.add(new Integer[] {s, last});
        tmp.add(new Integer[] {1, e});
      } else {
        tmp.add(new Integer[] {s, e});
      }
    }

    // 最大重叠区间个数求解
    tmp.sort((a, b) -> a[0] - b[0]);

    PriorityQueue<Integer> end = new PriorityQueue<>((a, b) -> a - b);

    int max = 0;
    int ans = tmp.get(0)[0];
    for (Integer[] range : tmp) {
      int s = range[0];
      int e = range[1];

      while (end.size() > 0) {
        Integer top = end.peek();

        if (top < s) {
          end.poll();
        } else {
          break;
        }
      }

      end.offer(e);

      if (end.size() > max) {
        max = end.size();
        ans = s;
      }
    }
    return ans;
  }
}

Python算法源码

import queue

# 输入获取
n = int(input())
ranges = [list(map(int, input().split())) for i in range(n)]


# 算法入口
def getResult(ranges):
    # 由于题目并未说有几个站点，因此需要计算出最后一个站点
    last = max(map(lambda x: max(x[0], x[1]), ranges))

    # 如果存在 [3,2] 这种坐车区间，即从站点3 -> 站点4 -> 站点1 -> 站点2，则此时将该坐车区间拆分为 [3, 4]和[1, 2]
    tmp = []
    for ran in ranges:
        s, e = ran

        if s > e:
            tmp.append([s, last])
            tmp.append([1, e])
        else:
            tmp.append(ran)
    ranges = tmp

    # 最大重叠区间个数求解
    ranges.sort(key=lambda x: x[0])
    end = queue.PriorityQueue()
    maxV = 0
    ans = ranges[0][0]

    for ran in ranges:
        s, e = ran

        while end.qsize() > 0:
            top = end.queue[0]

            if top < s:
                end.get()
            else:
                break

        end.put(e)

        if end.qsize() > maxV:
            maxV = end.qsize()
            ans = s

    return ans


print(getResult(ranges))

基于差分数列求解本题（更适合本题）

关于差分数列，请看

算法设计 – 前缀和 & 差分数列_伏城之外的博客-CSDN博客

然后可以尝试下leetcode下面差分数列题目

LeetCode – 1109 – 航班预定统计_伏城之外的博客-CSDN博客

本题差分数列求解的解析可以参照上面两个博客

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    n = lines[0] - 0;
  }

  if (n && lines.length === n + 1) {
    const ranges = lines.slice(1).map((line) => line.split(" ").map(Number));
    console.log(getResult(ranges));
    lines.length = 0;
  }
});

function getResult(ranges) {
  // 由于题目并未说有几个站点，因此需要计算出最后一个站点
  const last = Math.max.apply(null, ranges.toString().split(",").map(Number));

  const diff = new Array(last).fill(0);

  for (let range of ranges) {
    const [l, r] = range;
    if (l > r) {
      diff[l - 1] += 1;
      diff[0] += 1;
      diff[r] -= 1;
    } else {
      diff[l - 1] += 1;
      if (r < last) diff[r] -= 1;
    }
  }

  const preSum = [diff[0]];
  let max = preSum[0];
  let maxI = 0;
  for (let i = 1; i < last; i++) {
    preSum[i] = preSum[i - 1] + diff[i];
    if (preSum[i] > max) {
      max = preSum[i];
      maxI = i;
    }
  }

  return maxI + 1;
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[][] ranges = new int[n][2];

    for (int i = 0; i < n; i++) {
      ranges[i][0] = sc.nextInt();
      ranges[i][1] = sc.nextInt();
    }

    System.out.println(getResult(ranges));
  }

  public static int getResult(int[][] ranges) {
    // 由于题目并未说有几个站点，因此需要计算出最后一个站点
    int last =
        Arrays.stream(ranges)
            .map(range -> Math.max(range[0], range[1]))
            .max((a, b) -> a - b)
            .orElse(0);

    int[] diff = new int[last];

    for (int[] range : ranges) {
      int l = range[0];
      int r = range[1];

      if (l > r) {
        diff[l - 1] += 1;
        diff[0] += 1;
        diff[r] -= 1;
      } else {
        diff[l - 1] += 1;
        if (r < last) diff[r] -= 1;
      }
    }

    int[] preSum = new int[last];
    int max = preSum[0] = diff[0];
    int maxI = 0;
    for (int i = 1; i < last; i++) {
      preSum[i] = preSum[i - 1] + diff[i];
      if (preSum[i] > max) {
        max = preSum[i];
        maxI = i;
      }
    }

    return maxI + 1;
  }
}

Python算法源码

# 输入获取
n = int(input())
ranges = [list(map(int, input().split())) for i in range(n)]


# 算法入口
def getResult(ranges):
    # 由于题目并未说有几个站点，因此需要计算出最后一个站点
    last = max(map(lambda x: max(x[0], x[1]), ranges))

    diff = [0 for i in range(last)]

    for ran in ranges:
        l, r = ran
        if l > r:
            diff[l - 1] += 1
            diff[0] += 1
            diff[r] -= 1
        else:
            diff[l - 1] += 1
            if r < last:
                diff[r] -= 1

    preSum = [0 for i in range(last)]
    maxV = preSum[0] = diff[0]
    maxI = 0
    for i in range(1, last):
        preSum[i] = preSum[i - 1] + diff[i]
        if preSum[i] > maxV:
            maxV = preSum[i]
            maxI = i

    return maxI + 1


# 算法调用
print(getResult(ranges))

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

3、原文链接：https://moreit.club/?blog=a%e5%8d%b7100%e5%88%86-%e4%ba%ba%e6%95%b0%e6%9c%80%e5%a4%9a%e7%9a%84%e7%ab%99%e7%82%b9%ef%bc%88java-js-python%ef%bc%89，转载请注明出处。

2024华为OD机试题库