Interval scheduling：双组护士排班可行性验证问题（满足[1,t]时段双岗覆盖且组规模不超过I）

我来帮你拆解这个医院护士排班的问题，给出清晰的问题定义、约束条件和示例解法：

问题背景 #

医院需要确保在整数时段[1, t]内的每一个时刻，都至少有两名护士在岗。不过这里有个特殊要求：这两名护士必须分别来自两个不同的护士组G₁和G₂，而且每个组的人数不能超过给定的阈值I。

每名护士都有自己的可用工作区间{startₖ, endₖ}，你可以灵活安排他们在自己的可用区间内的上岗/离岗时间，只要能达成最优的排班效果就行。

核心问题 #

我们需要判断：是否能从现有的n名护士中划分出两个组G₁和G₂，满足：

• 组规模限制：|G₁| ≤ I，|G₂| ≤ I
• 全时段覆盖要求：对于[1, t]里的任意时刻，G₁至少有一名护士在岗，同时G₂也至少有一名护士在岗

示例输入 #

nurses_availability: [ {1, 5}, {1, 6}, {5, 6}, {8, 10}, {6, 10}, {6, 8}, {7, 10} ]
I = 3
t = 10

示例可行方案 #

• G₁ = [ {1, 5}, {6, 10} ]（组规模为2，满足≤3的约束）
• G₂ = [ {1, 6}, {6, 8}, {7, 10} ]（组规模为3，刚好达到阈值I）

覆盖验证 #

针对1到10的每个整数时刻，两组的在岗情况都满足要求：

• 时刻1-5：G₁有{1,5}在岗，G₂有{1,6}在岗
• 时刻6：G₁有{6,10}在岗，G₂有{1,6}、{6,8}在岗
• 时刻7-8：G₁有{6,10}在岗，G₂有{6,8}、{7,10}在岗
• 时刻9-10：G₁有{6,10}在岗，G₂有{7,10}在岗

内容的提问来源于stack exchange，提问作者MOE