java - 在两个数组中找到最大时间窗口。 StartArray和EndArray

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

例如，如果我有：

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

所以我可以从5到10、7到11、2到6租用我的大厅。从这3种组合中，最适合我的是去2到6，然后是7到11。离开5到10（因为礼堂已经租金）。

谁能帮我解释一下逻辑吗？从几个小时以来我一直在努力，我想现在我的头会爆裂。

最佳答案

可以这么说，解决方案的关键是贪婪算法。您可以在此处阅读有关此算法的更多信息：

Useful article on WiKi about maximum disjoint sets of objects

可能的解决方案之一：

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]