主体思路
做法1:基于贪心思想,模拟区间合并的过程
区间挨不在一起,就算两个区间;否则(end > cur.left),合并区间(延展区间的右边, end = max(end, cur.right))
最后统计合并后的区间数
做法2:差分思想
把区间[l, r]看成两个事件:在l处+1,在r处-1
建一个二元组events {ene, effect}, ene标记区间左右端位置,effect标记是开始(1)还是结束(-1),遍历这些区间,生成[]events,把这组排序一下,得到总的“时间线”。
遍历该“时间线”,用count来标记事件状态:count一开始是0,后来变成1,这就是区间开始了,再变成0,表明区间(合并)结束。
这比做法1思路会更简单一点,而且省写一次max函数
注意细节
两种方法中的结构体序列含义不一样,但是排序的逻辑还是一样的
基础代码 做法1
package main
import (
"bufio"
"os"
"strings"
"strconv"
"sort"
"fmt"
)
var (
out = bufio.NewWriter(os.Stdout)
in = bufio.NewScanner(os.Stdin)
bs = make([]byte, 20000 * 1024)
readLine = func() (res []int) {
in.Scan()
l := strings.Split(in.Text(), " ")
res = make([]int, len(l))
for i, s := range l {
x, _ := strconv.Atoi(s)
res[i] = x
}
return
}
)
type pair struct {
left int
right int
}
func merge(a []pair) int {
max := func(a, b int) int { if a > b { return a }; return b }
sort.Slice(a, func(i, j int) bool {
if a[i].left == a[j].left { return a[i].right < a[j].right }
return a[i].left < a[j].left
})
res := []pair{}
start, end := -1 << 31, -1 << 31
for _, cur := range a {
if end < cur.left {
if start != -1 << 31 { res = append(res, pair{start, end}) }
start = cur.left; end = cur.right
} else { end = max(end, cur.right) } // 延展区间的右边
}
if start != -1 << 31 { res = append(res, pair{start, end}) } // 新开一段
return len(res)
}
func main() {
in.Buffer(bs, len(bs))
cur, array := readLine(), []pair{}
n := cur[0]
for i := 0; i < n; i++ {
cur := readLine()
array = append(array, pair{cur[0], cur[1]})
}
fmt.Fprint(out, merge(array))
out.Flush()
}
做法1的进阶写法
package main
import (
"fmt"
"os"
"strings"
"strconv"
"bufio"
"sort"
)
type p struct {
l, r int
}
type pair []*p
var (
out = bufio.NewWriter(os.Stdout)
in = bufio.NewScanner(os.Stdin)
readLine = func() []int {
in.Scan()
l := strings.Split(in.Text(), " ")
res := make([]int, len(l))
for i, s := range l {
x, _ := strconv.Atoi(s)
res[i] = x
}
return res
}
)
func max(i, j int) int {if i > j {return i}; return j}
func (a pair) merge() int {
sort.Slice(a, func(i, j int) bool {
if a[i].l == a[j].l {return a[i].r > a[j].r}
return a[i].l < a[j].l
})
res := pair{}
start, end := -1 << 31 - 1, -1 << 31 - 1
for _, c := range a {
if end < c.l {
if start != -1 << 31 - 1 {res = append(res, &p{start, end})}
start, end = c.l, c.r
} else {
end = max(end, c.r)
}
}
if start != -1 << 31 - 1 {res = append(res, &p{start, end})}
return len(res)
}
func main() {
t := readLine()
n := t[0]
all := pair{}
for ; n > 0; n-- {
t = readLine()
all = append(all, &p{t[0], t[1]})
}
fmt.Fprint(out, all.merge())
out.Flush()
}
基础代码:做法2
package main
import (
"bufio"
"os"
"strings"
"strconv"
"sort"
"fmt"
)
var (
out = bufio.NewWriter(os.Stdout)
in = bufio.NewScanner(os.Stdin)
bs = make([]byte, 20000 * 1024)
readLine = func() (res []int) {
in.Scan()
l := strings.Split(in.Text(), " ")
res = make([]int, len(l))
for i, s := range l {
x, _ := strconv.Atoi(s)
res[i] = x
}
return
}
)
type enevts struct {
ene int // 事件发生位置
effect int // 发生事件, 1:区间开始, -1:区间结束
}
func merge(a []enevts) int {
sort.Slice(a, func(i, j int) bool { // 按位置(开始 > 结束)排序
if a[i].ene == a[j].ene { return a[i].effect > a[j].effect }
return a[i].ene < a[j].ene
})
res := []enevts{}
count, left := 0, 0 // count标志当前事件的状态,1:在前面已经开始新的区间, 0:没有开始区间
for _, cur := range a {
if count == 0 { left = cur.ene }
count += cur.effect
if count == 0 { res = append(res, enevts{left, cur.ene}) } // 这里count经历了从0,1,0之后,已经合并好一个区间,把该区间存进res
}
return len(res)
}
func main() {
in.Buffer(bs, len(bs))
cur, array := readLine(), []enevts{}
n := cur[0]
for i := 0; i < n; i++ {
cur := readLine()
array = append(array, enevts{cur[0], 1})
array = append(array, enevts{cur[1], -1})
}
fmt.Fprint(out, merge(array))
out.Flush()
}
做法2的进阶写法
package main
import (
"fmt"
"os"
"bufio"
"strings"
"strconv"
"sort"
)
type e struct { // 记录事件的结构体,idx:事件发生位置,eff:“1”区间开始,“-1”区间结束
idx, eff int
}
type event []*e // 事件序列
type interval struct { // 区间结构体,l, r 区间的左右两端
l, r int
}
var (
out = bufio.NewWriter(os.Stdout)
in = bufio.NewScanner(os.Stdin)
readLine = func() []int {
in.Scan()
l := strings.Split(in.Text(), " ")
res := make([]int, len(l))
for i, s := range l {
x, _ := strconv.Atoi(s)
res[i] = x
}
return res
}
)
func (a event) merge() int {
sort.Slice(a, func(i, j int) bool {
if a[i].idx == a[j].idx {return a[i].eff > a[j].eff}
return a[i].idx < a[j].idx
})
res := []*interval{}
count, left := 0, 0
for _, c := range a {
if count == 0 {left = c.idx}
count += c.eff
if count == 0 {res = append(res, &interval{left, c.idx})}
}
return len(res)
}
func main() {
p := readLine()
n := p[0]
all := event{}
for ; n > 0; n-- {
p = readLine()
all = append(all, &e{p[0], 1})
all = append(all, &e{p[1], -1})
}
fmt.Fprint(out, all.merge())
out.Flush()
}