Объединение перекрывающихся интервалов с использованием двойного цикла for

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
}

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}]

Answer 2

единственное «добавление» происходит во время следующего фрагмента кода.

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

Итак, глядя на {0,1} и остальные:

• 1 <[3,4,10,9] </li>
• Таким образом, перекрытия нет, и оно игнорируется.
• Помимо вашего вопроса, вы можете попробовать проверить кортеж, который полностью включен в другой кортеж, например {6,7};)
• Также вы можете снова и снова выполнять свой алгоритм в наборе решений, пока он не будет отличаться от предыдущего запуска. Может быть, дополнительные {3,4} могут спровоцировать это?