目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码

题目描述

某公司组织一场公开招聘活动，假设由于人数和场地的限制，每人每次面试的时长不等，并已经安排给定，用(S1,E1)、 (S2,E2)、 (Sj,Ej)…(Si < Ei，均为非负整数)表示每场面试的开始和结束时间。

面试采用一对一的方式，即一名面试官同时只能面试一名应试者，一名面试官完成一次面试后可以立即进行下一场面试，且每个面试官的面试人次不超过 m。

为了支撑招聘活动高效顺利进行，请你计算至少需要多少名面试官。

输入描述

输入的第一行为面试官的最多面试人次 m，第二行为当天总的面试场次 n，

接下来的 n 行为每场面试的起始时间和结束时间，起始时间和结束时间用空格分隔。

其中， 1 <= n, m <= 500

输出描述

输出一个整数，表示至少需要的面试官数量。

用例

题目解析

本题要想面试官人数最少，则需要每个面试官面试尽量多的人。

我们将每个面试官想象成一个桶，每个面试者想象成一个球。

首先，我们需要对面试者的面试时间段，按照开始时间进行升序。

由于不知道面试官个数，因此初始化时，有几个面试者就预定几个面试官，比如用例中有5个面试者，那就是初始化预定5个面试官。

接着，就是球放桶的问题了。

第一个球，放第一个桶。

第二个球，先尝试放第一个桶，首先检查桶中球个数是否已达到m，若已达到，则不能放入，继续尝试放入下一个桶，若未达到，则将球和桶最上面的球比较，即看面试时间是否有交集，如果有交集，则不能放入，继续尝试放入下一个桶，如果没有交集，则可以放入。

按照上面逻辑，放入所有球。

然后把空桶排除掉，剩下还有几个桶，就需要几个面试官。

算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];
let m, n;
rl.on("line", (line) => {lines.push(line);if (lines.length === 1) {m = lines[0] - 0;}if (lines.length === 2) {n = lines[1] - 0;}if (n && lines.length === n + 2) {const arr = lines.slice(2).map((line) => line.split(" ").map(Number));console.log(getResult(arr, m, n));lines.length = 0;}
});function getResult(arr, m, n) {arr.sort((a, b) => a[0] - b[0]);const buckets = new Array(n).fill(0).map(() => new Array());for (let area of arr) {for (let bucket of buckets) {if (bucket.length < m &&(bucket.length === 0 || !hasIntersection(bucket.at(-1), area))) {bucket.push(area);break;}}}return buckets.filter((bucket) => bucket.length !== 0).length;
}function hasIntersection(area1, area2) {const [s1, e1] = area1;const [s2, e2] = area2;if (s1 > s2) return s1 <= e2;else if (s1 < s2) return s2 <= e1;else return true;
}