题解 | #合并区间#

package main

import . "nc_tools"

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

/**
 *
 * @param intervals Interval类一维数组
 * @return Interval类一维数组
 */

/*
*
给出一组区间，请合并所有重叠的区间。
请保证合并后的区间按区间起点升序排列。
*/
func merge(intervals []*Interval) []*Interval {
	dp := make([]int, 400010)
	for _, interval := range intervals {
		dp[interval.Start*2]++
		dp[interval.End*2+1]--
	}
	res := make([]*Interval, 0)
	st := -1
	for i := 0; i < len(dp); i++ {
		if i > 0 {
			dp[i] += dp[i-1]
		}
		if dp[i] > 0 {
			if st < 0 {
				st = i
			}

		} else {
			if st >= 0 {
				interval := &Interval{Start: st / 2, End: (i - 1) / 2}
				res = append(res, interval)
				st = -1
			}
		}
	}
	return res
	// write code here
}