区间派工问题属于NPC证明

为了证明区间派工问题属于NPC，需要证明以下两个条件：

1. 区间派工问题是一个NP问题。

2. 存在一个已知的NPC问题可以在多项式时间内约化成区间派工问题。

证明第一个条件：

首先，我们需要证明一个解可以在多项式时间内被验证。我们可以通过以下步骤来验证解：

• 检查每个工人被分配的任务是否符合他们的能力和空闲时间。
• 检查每个任务是否在一个工人的空闲时间内完成。
• 检查每个任务是否只被分配给一个工人。

这些验证步骤可以在多项式时间内完成，因此，区间派工问题是一个NP问题。

证明第二个条件：

我们需要证明，存在一个已知的NPC问题可以在多项式时间内约化成区间派工问题。我们可以选择3-CNF-SAT问题来约化。

3-CNF-SAT问题是指，给定一个由多个3个变量的布尔公式组成的集合，每个变量都是true或false，问题是找到一组变量的赋值，使得每个公式都为true。

我们可以将3-CNF-SAT问题转换为区间派工问题，具体步骤如下：

• 创建一个工人集合，每个工人对应一个变量。
• 创建一个任务集合，每个任务对应一个公式。
• 对于每个公式，创建三个时间段，每个时间段对应公式中的一个变量。
• 如果公式中的某个变量为正，则将对应的时间段分配给对应的工人；如果变量为负，则将对应的时间段分配给对应的工人的相反时间段。

通过这种方式，我们可以将3-CNF-SAT问题转换为区间派工问题。

因此，我们证明了区间派工问题属于NPC。