algorithm - 这个 MSP 是 TSP 的一个实例吗？

Question

Steven S. Skiena 在他的算法设计手册一书中提出了以下问题:

Now consider the following scheduling problem. Imagine you are a highly-indemand actor, who has been presented with offers to star in n different movie projects under development. Each offer comes specified with the first and last day of filming. To take the job, you must commit to being available throughout this entire period. Thus you cannot simultaneously accept two jobs whose intervals overlap.

For an artist such as yourself, the criteria for job acceptance is clear: you want to make as much money as possible. Because each of these films pays the same fee per film, this implies you seek the largest possible set of jobs (intervals) such that no two of them conflict with each other.

For example, consider the available projects in Figure 1.5 [above]. We can star in at most four films, namely “Discrete” Mathematics, Programming Challenges, Calculated Bets, and one of either Halting State or Steiner’s Tree.

You (or your agent) must solve the following algorithmic scheduling problem:

Problem: Movie Scheduling Problem

Input: A set I of n intervals on the line.

Output: What is the largest subset of mutually non-overlapping intervals which can be selected from I?

我想知道，这是 TSP 的一个实例(也许是一个简化的实例)吗？

Answer 1

这个问题可以通过简单地选择完成日期最早的电影来解决，然后从那里开始，O(n^2) 过程(可能有更快的解决方案)。由于我们找到了多项式时间解，因此它不是 TSP 的实例，除非:(1) P=NP，以及 (2) (1) 的证明非常简单。