AcWing 907. 区间覆盖
原题链接
简单
作者:
Sam_2
,
2020-10-05 09:57:51
,
所有人可见
,
阅读 389
package main
import(
"fmt"
"math"
"sort"
)
type Pair struct {
l int
r int
}
type PairArray []*Pair
func (p PairArray) Len() int {
return len(p)
}
func (p PairArray) Less(i, j int) bool {
return p[i].l < p[j].l
}
func (p PairArray) Swap(i, j int) {
(p)[i], (p)[j] = (p)[j], (p)[i]
}
func main() {
var start, end int
fmt.Scanf("%d", &start)
fmt.Scanf("%d", &end)
var n, l, r int
fmt.Scanf("%d", &n)
pairarray := make([]*Pair, n)
for i := 0; i < n; i++ {
fmt.Scanf("%d%d", &l, &r)
pairarray[i] = &Pair{
l: l,
r: r,
}
}
sort.Sort(PairArray(pairarray))
max := math.MinInt32
succ := false
res := 0
for i := 0; i < n; i++ {
j := i
for ; j < n && pairarray[j].l <= start; j++ {
if max < pairarray[j].r {
max = pairarray[j].r
}
}
res++
if max < start {
break
}
if max >= end {
succ = true
break
}
start = max
i = j-1
}
if succ {
fmt.Printf("%d\n", res)
return
}
fmt.Printf("-1\n")
}