题目描述
算法1
按照右端点排序,随后遍历每个区间,如果有左端点在上一个区间点(右端点)后面有间隔端点,则表示上一个区间点无法覆盖(有断点),所以要加一个点。随后上一区间点置为该区间右端点(也就是该选区间选点能覆盖最大的位置)
(暴力枚举) $O(nlogn)$
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
struct Range
{
int l, r;
bool operator< (const Range &W)const //需要重载比大小,因为后续sort方法需要按第二个,r 这个field成员变量排
{
return r < W.r;
}
}range[N];
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i ++ ){
cin >> range[i].l >> range[i].r;
}
// 按右端点排序:
sort(range, range + n);
int ed = -2e9;
int res = 0;
for (int i = 0; i < n; i ++ ){
if (ed < range[i].l){
res ++;
ed = range[i].r;
}
}
cout << res << endl;
return 0;
}
算法2
时间复杂度
参考文献
Golang 代码
package main
import(
"fmt"
"sort"
"os"
"bufio"
)
type Pair struct {
l int
r int
}
func main(){
var n int;
//const N = 100010;
// Create a slice of Pair with length N
//var slice []int = make([]Pair, 3)
fmt.Fscan(reader, &n)
//fmt.Scanf("%d", &n);
slice := make([]Pair, n)
for i := 0; i < n;i++{
fmt.Fscan(reader, &slice[i].l, &slice[i].r)
//fmt.Scanf("%d %d", &slice[i].l, &slice[i].r);
//fmt.Printf("%d %d", slice[i].l, slice[i].r);
}
sort.Slice(slice, func(i, j int) bool {
return slice[i].r < slice[j].r //这里换成slice[i].l可以按l左端点排序
})
// Print the sorted slice
res := 0
var ed int
ed = -2e9
for i := 0; i < n; i++{
if (ed < slice[i].l){
res ++
ed = slice[i].r
}
}
fmt.Println(res)
/*
fmt.Println("Sorted by r field:")
for _, pair := range slice {
fmt.Printf("l = %d, r = %d\n", pair.l, pair.r)
}*/
//return 0
}
通过了9/11 TLE超时了