Skip to content

Instantly share code, notes, and snippets.

@bemasher
Created March 20, 2013 01:13
Show Gist options
  • Save bemasher/5201562 to your computer and use it in GitHub Desktop.
Save bemasher/5201562 to your computer and use it in GitHub Desktop.
package main
import (
"fmt"
"sort"
"time"
"math/rand"
)
const (
N = 4
)
type Range struct {
Min, Max int
}
type RangeMap map[int]int
// Given a list of ranges, add them to the map
func (r RangeMap) MergeList(l []Range) {
for _, i := range l {
// Set the value for the lower bound key if it doesn't exist in the
// map or if the existing value is smaller than the current bound
if v, exists := r[i.Min]; !exists || v <= i.Max {
r[i.Min] = i.Max
}
}
}
// Return the list of merged intervals
func (r RangeMap) List() (p []Range) {
// Create a list of all interval lower bounds
mins := make([]int, 0)
for k := range r {
mins = append(mins, k)
}
// Sort the starting values since map iteration
// order in golang is undefined
sort.Ints(mins)
var (
prev *int
max int
)
// For each interval lower bound
for _, min := range mins {
max = r[min]
// If there is no previous range or this interval doesn't overlap
// with the previous interval, append it to the result list
if prev == nil || *prev < min {
p = append(p, Range{min, max})
prev = &p[len(p)-1].Max
// Move on to next interval from the map
continue
}
// If the current interval overlaps the previous range and the
// current interval is larger than the previous upper bound, set
// the previous upper bound to the current interval's upper bound
if *prev >= min && *prev < max {
*prev = max
}
}
return
}
func main() {
// Generate a random list of intervals to merge
l := make([]Range, 0)
r := rand.New(rand.NewSource(time.Now().UnixNano()))
fmt.Printf("Generating %d ranges with intervals smaller than %d in the range (0, %d)...\n", N << 3, N << 3, N << 6)
for len(l) < N << 3 {
lower, upper := r.Intn(N << 6), r.Intn(N << 6)
if lower <= upper && upper - lower < N << 3 {
l = append(l, Range{lower, upper})
}
}
fmt.Println(len(l), l)
fmt.Println()
rm := make(RangeMap)
rm.MergeList(l)
fmt.Println("Merged Intervals:")
pairs := rm.List()
fmt.Println(len(pairs), pairs)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment