javascript - 从一组约会中获取重叠时间范围的列表

Question

标题不是很好，我愿意接受建议。

这是我的基本问题:

我有一组约会，每个约会都有开始时间和结束时间。

鉴于该集合，我想要的是一组新的范围 [ start_time, end_time ]，适用于 n 重叠约会的所有时间段。

因此，例如，给定集合(为了便于阅读，时间戳简化为小数字)

[
[ 1, 3 ],
[ 2, 4 ],
[ 2, 4 ],
[ 5, 7 ],
[ 6, 8 ],
[ 7, 8 ]
]


...假设我想要所有范围内至少有 3 个不同的约会，结果应该是

[
[ 2, 3 ],
[ 6, 7 ]
]


为了让它不那么抽象......

想象一下，我运行一个 24 小时窗口着色服务，始终有 3 名安装人员在岗。在我的网站上，我想显示所有可用的安装时间。所以我需要隐藏我已经安排了 3 个约会的任何时间范围。

不一定要求任何人编写代码 - 但如果有人可以为我指出此类问题的知名算法，我将不胜感激。

谢谢。

[编辑] 添加了 javascript 标签，因为我将在 Node 中实现它，但答案不需要在 JS 中。

[编辑 2] 我正在寻找一个非常通用的解决方案，所以假设约会可以随时开始(未标准化为一小时或 30 分钟)并且可以持续任何时间

Answer 1

我认为从输入范围创建直方图，然后遍历直方图定位范围，其中高度大于或等于目标重叠，在本例中为 3。

顺便说一句，根据您的输入，我认为 [6,7] 不是有效范围 - 我认为它应该是 [7,7]。至少那是我的代码产生的:)

下面是一些 Java 代码来说明:

public static void main(String[] args)
{
    int[][] ranges = {{1,3},{2,4},{2,4},{5,7},{6,8},{7,8}};

    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for(int[] range : ranges) 
    {
        min = Math.min(min, range[0]);
        max = Math.max(max, range[1]);
    }       

    int[] hist = new int[1+max-min];
    for(int[] range : ranges) 
        for(int i=range[0]; i<=range[1]; i++) hist[i-min]++;

    int overlap = 3;
    for(int i=0; i<hist.length; i++)
    {
        int j = i;
        while(i<hist.length && hist[i] >= overlap) {i++;}
        if(i>j) 
            System.out.println((j+min) + " : " + (i+min-1));
    }
}

输出:

2 : 3
7 : 7

编辑

我对直方图方法不满意，因为它依赖于整数范围并且对于长范围来说效率低下。在我看来，您可以改为对范围端点进行排序，跟踪它们是在范围的开始还是结束，然后遍历端点以保持事件范围的计数器(遇到开始时递增，遇到开始时递减遇到一个尽头)。当计数器首次升至高于或低于您的阈值时，在您的情况 3 中，您将输出范围。

我现在看到 MBo 建议采用相同的方法。

这里还有一些代码来说明:

static class RangeEnd
{
    int time;
    int delta;
    public RangeEnd(int pos, int delta)
    {
        this.time = pos;
        this.delta = delta;
    }
}

public static void main(String[] args)
{
    int[][] ranges = {{ 1,3},{2,4},{2,4},{5,7},{6,8},{7,8}};

    RangeEnd[] ends = new RangeEnd[2*ranges.length];

    int i=0;
    for(int[] range : ranges) 
    {
        ends[i++] = new RangeEnd(range[0], 1);
        ends[i++] = new RangeEnd(range[1], -1);
    }

    Arrays.sort(ends, new Comparator<RangeEnd>()
    {

        @Override
        public int compare(RangeEnd e1, RangeEnd e2)
        {
            if(e1.time < e2.time) return -1;
            else if(e1.time > e2.time) return 1;
            else if (e1.delta > e2.delta) return -1;
            else return 1;
        }
    });

    int overlap = 3;

    int count = 0;
    boolean active = false;
    int start = 0;
    for(RangeEnd end : ends)
    {
        count += end.delta;
        if(count >= overlap)
        {
            if(!active)
            {
                start = end.time;
                active = true;
            }
        }
        else if(active)
        {
            System.out.println(start + " : " + end.time);
            active = false;
        }
    }
}