在两个数组中查找最大时间窗口数.StartArray和EndArray

Question

我有两个Integer数组，StartArray和EndArray。StartArray包含研讨会开始的时间，EndArray包含相应的结束时间。我有一个礼堂要租。当我能做到这一点时，我想找到最大的组合。

例如，如果我有：

int[] startArray = {5,7,2};
int[] endArray = {10,11,6};

所以我可以在5点到10点、7点到11点、2点到6点租我的大厅。在这三个组合中，对我来说最好的是2比6，然后是7比11。5点到10点离开（因为礼堂已经在租了）。

有人能帮我讲一下逻辑吗？我几个小时以来一直在做这件事，我想我现在会崩溃的。

Answer 1

据说，解决方案的关键是贪婪算法。关于这个算法的更多信息，你可以在那里阅读：

WiKi上关于对象的最大不相交集的有用文章

可能的解决方案之一：

1） 声明一个类来表示分段：

class Segment implements Comparable<Segment> {
    int left;
    int right;
    Segment(int left, int right) {
        this.left = left;
        this.right = right;
    }
    @Override
    public int compareTo(Segment segment) {
        return segment.left - left;
    }
    @Override
    public String toString() {
        return "[" + left + "," + right + "]";
    }
}

2） 声明一个主类：

import java.util.ArrayList;
import java.util.Collections;
public class MaximumDisjointSet {
    public static void main(String[] args) {
        // List of all segments
        ArrayList<Segment> segments = new ArrayList<>();
        // Add segments
        segments.add(new Segment(5, 10));
        segments.add(new Segment(7, 11));
        segments.add(new Segment(2, 6));
        // Sort all segments by their left endpoint in descending order
        Collections.sort(segments);
        // Store the left endpoint of last accepted segment,
        // initially it's useful to assign it "infinity"
        int lastAcceptedLeftPoint = Integer.MAX_VALUE;
        for (Segment segment : segments) {
            // Accept current segment if it's right endpoint is lesser
            // than the left endpoint of last accepted segment
            if (segment.right < lastAcceptedLeftPoint) {
                lastAcceptedLeftPoint = segment.left;
                System.out.println(segment);
            }
        }
    }
}

输出为：

[7,11]
[2,6]