在重叠区间中查找基本区间

Question

我在准备一些编程面试时遇到了一个很好的问题。

给定一组可能重叠的区间，您需要编写一个函数来返回其中的所有基本区间。例如：如果给定的间隔为以下对列表：{{1,5}、{3,10}、{5,11}、{15,18}、{16,20}}，那么您需要返回以下内容：

{1,3}, {3,5}, {5,10}, {10,11}, {15,16}, {16,18}, {18,20}}

{ 跟随在上面的答案：

• 答案中省略了区间{11,15}，因为它是 输入中不存在。
• 输入的区间 {1,5} 已分为 {1,3}、{3,5} 在答案中，因为在 {3,10} 中定义了起点“3” 将区间分割为两个基本区间的输入。

Java 中的方法签名：

List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer> intervals)

我想象的解决方案之一是将输入分成不相交的集合，然后对每个不相交的集合中的所有数字进行简单的 O(NlogN) 排序将产生答案。有更有效的方法吗？

Answer 1

您可以先将此问题分解为嵌套区间，然后分别处理每个嵌套。我所说的嵌套是指至少共享一个点的间隔。对于您给出的示例：

{{1,5}, {3,10}, {5,11}, {15,18}, {16,20}}

有两个嵌套：

{1,5}, {3,10}, {5,11}

并且

{15,18}, {16,20}

一般来说，要确定嵌套，您可以根据左端点对间隔进行排序（如您的示例中所示），然后每当看到 {x,y}, {x',y'} 且 y < x'。

对于嵌套，“基本间隔”由值的排序序列（不重复）形成。在示例中，嵌套给出

(1,3,5,10,11) -> {1,3}, {3,5}, {5,10}, {10,11}

和

(15,16,18,20) -> {15,16}, {16,18}, {18,20}

因此，整体算法可能如下所示：

• 根据左端点对间隔进行排序
• 运行间隔直到 {x,y}, {x',y'} <代码> y < x'
• 从开始到 {x,y}，制作端点排序列表（无重复），例如 a0,a1,...,ak
• 添加基本间隔 {ai,a(i+1)} for i = 0...k-1
• 删除直到 {x,y} 的间隔代码> 并从步骤 2 继续

Answer 2

您可以对端点进行排序，然后按顺序迭代。为了知道您是进还是出，您可以保留覆盖每个点的间隔数。
区间的左端贡献+1，而右端贡献-1：
（请注意，我使用 TreeMap，这是已排序）

static class Pair<T, K> {
    public Pair(T first, K second){
        this.first = first;
        this.second = second;
    }

    public String toString(){
        return "(" + first + ", " + second + ")";
    }

    T first;
    K second;   
}    

static List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer>> intervals) {
    TreeMap<Integer, Integer> overlaps = new TreeMap<Integer, Integer>();
    for(Pair<Integer, Integer> interval : intervals){
        int value = overlaps.containsKey(interval.first) ? overlaps.get(interval.first)+1 : 1;
        overlaps.put(interval.first, value);

        value = overlaps.containsKey(interval.second) ? overlaps.get(interval.second)-1 : -1;
        overlaps.put(interval.second, value);
    }

    List<Pair<Integer, Integer>>  retValue = new ArrayList<Pair<Integer,Integer>>();

    int overlap = 0;
    boolean in = false;
    int last = 0;
    for(int point : overlaps.keySet()){
        if(in)
            retValue.add(new Pair(last, point));

        overlap += overlaps.get(point);
        last = point;
        in = overlap > 0;
    }

    return retValue;
}    

public static void main(String[] args) {

    List<Pair<Integer, Integer>> l = new ArrayList<Pair<Integer, Integer>>();
    l.add(new Pair<Integer, Integer>(1,5));
    l.add(new Pair<Integer, Integer>(3,10));
    l.add(new Pair<Integer, Integer>(5,11));
    l.add(new Pair<Integer, Integer>(15,18));
    l.add(new Pair<Integer, Integer>(16,20));

    for(Object o : generateElementaryIntervals(l)){
        System.out.println(o.toString());
    }

}

Answer 3

一个简单的算法是简单地读取整个数字列表，并为每对中的每个项目创建一个元素。

每个元素将存储两个值：数字，以及它是第一个数字还是第二个数字（来自输入）。

然后，这些对将被排序，首先按其内部数字，然后按其位置（第二将排在第一之前）

以打印出间隔列表，您可以将每个数字与下一个数字一起打印，并遵循以下规则：

• 您不会打印重复的数字（例如，您不会打印 5,5）
• 如果您排他地有一个 第二个 数字，然后是第一个 数字，您不会打印该基本区间，因为该范围内没有值。