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

区间排工问题（Interval Scheduling Problem）是指给定一组工作，每个工作都有一个开始时间和结束时间，要求从中选择尽可能多的工作，使得这些工作之间不会发生时间上的冲突。该问题可以表示为：给定n个区间，选择尽可能多的区间，使得这些区间不相交。

证明该问题属于NPC，需要使用划分问题的归约。

假设存在一个算法A，可以在多项式时间内解决区间排工问题。现在考虑一个划分问题，即将一个集合S中的元素分成k个子集，使得每个子集的元素之和相等。该划分问题可以表示为：

输入：一个集合S和一个正整数k 输出：是否存在一种划分方式，使得S可以被分成k个子集，且每个子集的元素之和相等。

现在将该划分问题归约到区间排工问题的形式。具体地，将集合S中的每个元素i映射到一个区间'[start(i), end(i)]'，其中区间长度为i的值。然后将k映射到一个整数m，使得m等于S中所有元素值之和的一半。

现在，如果存在一种划分方式，使得S可以被分成k个子集，且每个子集的元素之和相等，那么将S中每个子集映射到一个区间，这些区间之间没有重叠部分，因为每个子集的元素之和相等，所以它们对应的区间长度之和也相等。因此，区间排工问题中选择这些区间，就可以得到最大的不相交区间集合，即可得到一个解。

反之，如果存在一个最大的不相交区间集合，将这些区间对应的元素放在一起，得到一个集合S'。因为这些区间之间没有重叠部分，所以S'可以被分成k个子集，且每个子集的元素之和相等。因此，划分问题中存在一种划分方式，使得S可以被分成k个子集，且每个子集的元素之和相等。

综上所述，区间排工问题可以用来解决划分问题，因此区间排工问题属于NPC。