algorithm - 考虑持续时间和无重叠的最佳电影时间表

Question

我正在努力寻找一个好的策略来解决这个问题。我考虑过按持续时间对电影集合进行排序，但这似乎掩盖了重叠情况。有任何想法吗？

我正在考虑的另一件事是根据开始月份进行排序，然后作为 this problem 的扩展进行处理。 .

An actor is offered a set of movies for a certain (start month and duration). You have to select the movies the actor should do so that the actor can do the most number of movies in the year, without any overlaps.

It is assumed that movies start on the first of a month, and end on the last day. Months are of 30 days (should not be required?).

Answer 1

我编写了一些代码来演示解决方案。整体本质类似于什么Edward Peters mentioned .首先是按结束时间对电影进行排序。现在，总是贪婪地选择第一个选项。

为什么选择第一个选项有效？

在我们的例子中，我们的订单 A 有第一部电影，一些 a。假设有另一个排序 B，其中第一部电影是一些 b，这样 b ≠ a。必须有一个排序(我们已经知道 A 的存在)使得 A = {B – {b}} U {a}。显然，在B的情况下，b的时间最小；因为 b ≠ a，duration(b) >= duration(a)。

public class Optimum_Movie_Schedule {

    public static void main(String[] args) {
        Movie[] movies = new Movie[] {
            new Movie("f", 5, 9),
            new Movie("a", 1, 2),
            new Movie("b", 3, 4),
            new Movie("c", 0, 6),
            new Movie("d", 5, 7),
            new Movie("e", 8, 9)
        };

        // sort by endMonth; startMonth if endMonth clash
        Arrays.sort(movies);
        System.out.println(Arrays.toString(movies));

        System.out.println("Final list: ");
        System.out.print(movies[0] + " ");

        int cur = 0;
        for(int i = 1 ; i < movies.length ; i++) {
            if(movies[i].startMonth > movies[cur].endMonth) {
                System.out.print(movies[i] + " ");
                cur = i;
            }
        }
    }

    static class Movie implements Comparable<Movie> {
        String name;
        int startMonth;
        int endMonth;
        int duration;
        public Movie(String name, int start, int end) {
            this.name = name;
            this.startMonth = start;
            this.endMonth = end;
            this.duration = (end + 1) - start;
        }

        public int compareTo(Movie o) {
            if(this.endMonth < o.endMonth)
                return -1;

            if(this.endMonth == o.endMonth)
                if(this.startMonth < o.startMonth)
                    return -1;

            return 1;
        }

        public String toString() {
            return name + "("+ startMonth + ", " + endMonth + ")";
        }
    }
}