AcWing 908. 最大不相交区间数量
原题链接
简单
作者:
Sam_2
,
2020-10-05 12:46:40
,
所有人可见
,
阅读 506
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].r < (*p)[j].r
}
func (p *PairArray) Swap(i, j int) {
(*p)[i], (*p)[j] = (*p)[j], (*p)[i]
}
func main() {
var n, l, r int
fmt.Scanf("%d", &n)
pairarray := make([]*Pair, 0, n)
for i := 0; i < n; i++ {
fmt.Scanf("%d%d", &l, &r)
pairarray = append(pairarray, &Pair{
l:l,
r:r,
})
}
sort.Sort((*PairArray)(&pairarray))
res := 0
max_R := math.MinInt32
for i := 0; i < n; i++ {
if pairarray[i].l > max_R {
res++
max_R = pairarray[i].r
}
}
fmt.Printf("%d\n", res)
}