(a) Yes,
解法1：vertex cover 问题是一个 NP-complete问题，所有的P和NP问题都可以规约到vertex cover问题。 而Interval Scheduling 可以在多项式时间里面被解决，是P问题，所以可以规约到vertex cover问题上。
可以直接用吗？
解法2： 用点来表示需要执行一段时间的任务，如果两个任务没有时间重合，就用边连接起来。这样我们只要找到这个图的VertexCover就找到了Interval scheduling .只需要找到最大的vertex cover,判定大小>k就可以了。 问题的转化是多项式时间，所以所以 Inerval Scheduling ≤p Vertex Cover
(b)Unknown.
用点来表示需要执行一段时间的任务，如果两个任务有时间重合，就用边连接起来。这样我们只要找到这个图的Independent set 就找到了Interval scheduling . 问题的转化是多项式时间，所以所以 Inerval Scheduling ≤p Independent set. 相反，因为我们从之前的学习知道 Interval scheduling 是多项式可解的，也就是一个P问题。如果Independent set ≤p Intercal scheduling ， 可以得到P≤ NP , 这样就说明了P和NP问题可以相互规约就解决了P=NP的问题。因为P=NP还是未解的，所以Unknown。
首先该问题为NP问题，给定一个指派，我们通过验证人数是否≤k, 以及是否覆盖了所有的运动可以验证是否是一个可行解。
其次我们通过 Set cover problem ≤p Efficient Recruiting Problem 来证明 该问题是一个NP-complete问题。
Setcover问题：
实例：现在有一个集合U，其中包含了m个元素（注意，集合是无序的，并且包含的元素也是不相同的），现在n个集合，分别为B1、B2、...、Bn。并且这n个集合的并集恰好等于A集合，即：B1UB2UB3U...UBn=A。
问题：是否存在B集合的最小子集，且他们的并集也等于A集合？