package main

import (
	"sort"
)

// Interval ...
type Interval struct {
	Start int
	End   int
}

// Endpoint ...
type Endpoint struct {
	Val   int
	IsEnd bool
}

// PointSlice ...
type PointSlice []Endpoint

func (p PointSlice) Len() int { return len(p) }
func (p PointSlice) Less(i, j int) bool {
	// 1( 4) 4( 6) -> 1( 4( 4) 6)
	// important!
	if p[i].Val == p[j].Val {
		return p[j].IsEnd
	}
	return p[i].Val < p[j].Val
}
func (p PointSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }

/**
 * Definition for an interval.
 * type Interval struct {
 *	   Start int
 *	   End   int
 * }
 */
func mergeOld(intervals []Interval) (res []Interval) {
	points := []Endpoint{}
	for _, v := range intervals {
		points = append(points, Endpoint{v.Start, false})
		points = append(points, Endpoint{v.End, true})
	}
	sort.Sort(PointSlice(points))
	for i, cnt := 0, 0; i < len(points); i++ {
		if cnt == 0 {
			inter := Interval{points[i].Val, 0}
			res = append(res, inter)
		}
		if !points[i].IsEnd {
			cnt++
		} else {
			cnt--
			if cnt == 0 {
				res[len(res)-1].End = points[i].Val
			}
		}

	}
	return
}

// By : by which function to sort intervals
type By func(p, q *Interval) bool

// IntervalSorter : interface for sorting intervals
type IntervalSorter struct {
	intervals []Interval
	by        By
}

func (p *IntervalSorter) Len() int {
	return len(p.intervals)
}
func (p *IntervalSorter) Less(i, j int) bool {
	return p.by(&p.intervals[i], &p.intervals[j])
}
func (p *IntervalSorter) Swap(i, j int) {
	p.intervals[i], p.intervals[j] = p.intervals[j], p.intervals[i]
}

// Sort : usage: By(func).Sort(intervals)
func (by By) Sort(intervals []Interval) {
	is := &IntervalSorter{intervals, by}
	sort.Sort(is)
}

func startValue(p, q *Interval) bool {
	return p.Start < q.Start
}

/* func maxInt(x, y int) int {
	if x > y {
		return x
	}
	return y
} */

/**
 * Definition for an interval.
 * type Interval struct {
 *	   Start int
 *	   End   int
 * }
 */
func merge(intervals []Interval) (res []Interval) {
	if len(intervals) < 2 {
		return intervals
	}
	By(startValue).Sort(intervals)
	res = append(res, intervals[0])
	for i := 1; i < len(intervals); i++ {
		if intervals[i].Start > res[len(res)-1].End {
			res = append(res, intervals[i])
			continue
		}
		res[len(res)-1].End = maxInt(intervals[i].End, res[len(res)-1].End)
	}
	return
}

/* func main() {
	i1 := []Interval{{1, 3}, {2, 6}, {8, 10}, {15, 18}}
	i2 := []Interval{}
	i3 := []Interval{{1, 4}, {4, 5}, {5, 6}}
	i4 := []Interval{{1, 4}, {0, 1}}
	fmt.Println(merge(i1))
	fmt.Println(merge(i2))
	fmt.Println(merge(i3))
	fmt.Println(merge(i4))
} */