CODEWITHSUNDEEP
arraysalgorithmgo
Kyates
Kyates

Reputation: 51

Merging overlapping intervals using double for loop

I am trying to merge some overlapping "meeting" intervals.

Given intervals:

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

Merged intervals:

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

My first approach is a double for loop. However, my output comes out to be:

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

Which is omitting {0, 1} in my final result.

Code:

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
}

Upvotes: 4

Views: 402

Answers (2)

peterSO
peterSO

Reputation: 166569

For example,

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

Playground: https://play.golang.org/p/13uwiQtlxPJ

Output:

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

Upvotes: 4

j0j0j0
j0j0j0

Reputation: 97

the only "appending" happens during your following code snippet.

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

So looking at {0,1} and the others:

  • 1 < [3,4,10,9]
  • Thus there is no overlapping and it is ignored.
  • Apart from your question you may try to test a tuple which is fully included within another tuple like {6,7} ;)
  • Also you might execute your algorithm again and again on your solution set till it does not differ from the previous run. Maybe an additional {3,4} could provoke this?

Upvotes: 0

Related Questions