使用双重循环合并重叠区间

Question

我正在尝试合并一些重叠的“会议”时间段。

给定的时间段：

  [{0, 1}, {3, 5}, {4, 8}, {10, 12}, {9, 10}]

合并区间：

  [{0, 1}, {3, 8}, {9, 12}]

我的第一种方法是使用双重循环。然而，我的输出结果如下：

  [{3, 8}, {9, 12}]

这句话的意思是：“在我的最终结果中省略了 {0, 1}。”

代码：

type Meeting struct {
    startTime int
    endTime   int
}

func MergeIntervals(meetings []Meeting) []Meeting {

    var mergedMeetings []Meeting

    for i := 0; i < len(meetings); i++ {
        for j := i + 1; j < len(meetings); j++ {
            var first Meeting
            var second Meeting

            // the meeting with the earlier start time is the "first" meeting
            if meetings[i].startTime < meetings[j].startTime {
                first = meetings[i]
                second = meetings[j]
            } else {
                first = meetings[j]
                second = meetings[i]
            }

            if first.endTime >= second.startTime {
                mergedMeetings = append(mergedMeetings, Meeting{first.startTime, second.endTime})
            }
        }
    }

    return mergedMeetings
}

- Kyates

---

这不是编码问题，而是算法问题。首先在纸上制定算法。当你有了算法之后，编码就成了一个机械化的任务。当你有了算法和相应的实现时，使用调试器。 - zerkms

Answer 1

举例来说，

package main

import (
    "fmt"
    "sort"
)

type Interval struct {
    Lo, Hi int
}

func merge(ivs []Interval) []Interval {
    m := append([]Interval(nil), ivs...)
    if len(m) <= 1 {
        return m
    }

    sort.Slice(m,
        func(i, j int) bool {
            if m[i].Lo < m[j].Lo {
                return true
            }
            if m[i].Lo == m[j].Lo && m[i].Hi < m[j].Hi {
                return true
            }
            return false
        },
    )

    j := 0
    for i := 1; i < len(m); i++ {
        if m[j].Hi >= m[i].Lo {
            if m[j].Hi < m[i].Hi {
                m[j].Hi = m[i].Hi
            }
        } else {
            j++
            m[j] = m[i]
        }

    }
    return append([]Interval(nil), m[:j+1]...)
}

func main() {
    intervals := []Interval{{0, 1}, {3, 5}, {4, 8}, {10, 12}, {9, 10}}
    merged := merge(intervals)
    fmt.Println(intervals)
    fmt.Println(merged)
}

沙盒环境：https://play.golang.org/p/13uwiQtlxPJ

输出：

[{0 1} {3 5} {4 8} {10 12} {9 10}]
[{0 1} {3 8} {9 12}]

- peterSO

Answer 2

在你接下来的代码片段中，唯一的“追加”发生在这里。

if first.endTime >= second.startTime {
                mergedMeetings = append(mergedMeetings, Meeting{first.startTime, second.endTime})
}

因此看一下 {0, 1} 和其他内容:

• 1 < [3,4,10,9]
• 因此没有重叠部分，被忽略了。
• 除了你的问题，你可以尝试测试一个完全包含在另一个元组中的元组，例如 {6,7} ;)
• 此外，您可能会多次在解集上执行算法，直到它与上一次运行时不同。也许会有另一个 {3,4} 引发这个结果？

- j0j0j0

---

这确实是代码错误的正确原因。 - leaf bebop