区间排工问题是NPC问题：划分问题归约证明

首先，我们需要证明区间排工问题是一个NP问题。对于一个给定的排工方案，我们可以在多项式时间内验证它是否满足以下两个条件：

对于每个工人，他们在不同的时间段工作；
每个时间段只能由一个工人工作。

因此，区间排工问题是一个NP问题。

接下来，我们需要证明区间排工问题可以通过多项式时间归约到划分问题。假设我们有一个区间排工问题的实例，其中有n个工人和m个时间段。我们可以构造一个划分问题的实例，其中有n个元素，每个元素的权重为对应工人能够工作的时间段数。我们将所有时间段按照起始时间从小到大排序，并依次将它们分配给每个工人。对于一个工人，如果他能够工作某个时间段，则我们将划分问题实例中对应的元素权重加上1。

现在我们证明这个归约的正确性。首先，如果我们能够找到一个划分，使得每个子集的元素权重之和都相等，则说明我们可以将所有时间段恰好分配给所有工人，满足区间排工问题的要求。

反之，如果我们能够找到一个区间排工方案，使得每个工人能够工作相同数量的时间段，则说明我们可以将划分问题实例中的元素划分为相等的子集。因为每个工人都能够工作相同数量的时间段，所以每个子集的元素权重之和也相等。

因此，我们证明了区间排工问题可以通过多项式时间归约到划分问题，而划分问题是NP完全的，所以区间排工问题也是NP完全的。