A contradiction arises, since J was assumed to not intersect with any interval in EFT(I), yet J is in EFT(I), and J intersects with itself. However, this would also mean that J is compatible with every interval in EFT(I), and so the earliest finishing time algorithm would have added J into EFT(I), and so J ∈ EFT(I). By definition of h, this means that no interval in EFT(I) intersects with J. Assume for a contradiction that there is no interval J' ∈ EFT(I) satisfying h(J) = J'. Show that h is a function mapping OPT(I) to EFT(I). Suppose J is an arbitrary interval in OPT(I). To show that the earliest finish time algorithm is optimal using the charging argument, h must be shown to be a one-to-one function mapping intervals in OPT(I) to those in EFT(I). For any interval J ∈ OPT(I), define h(J) as the interval J' ∈ EFT(I) that intersects J with the earliest finishing time amongst all intervals in EFT(I) intersecting J. Given a set of n intervals I =, let OPT(I) be any optimal solution of the interval scheduling problem, and let EFT(I) be the solution of the earliest finishing time algorithm. Consider the interval scheduling problem.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |