$$\color{Red}{区间选点=三种语言PII版和贪心版}$$
我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
给定 N 个闭区间 [ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。位于区间端点上的点也算作区间内。
方法一 区间合并PAIR模板
1.算法细节
- 没什么太大区别,每次答案的ed更新为重合部分较小值即可
2.具体代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
int n, a, b;
int main()
{
cin >> n;
vector<PII> q, ans;
for(int i=0; i<n; i++)
{
cin >> a >> b;
q.push_back({a,b});
}
sort(q.begin(), q.end());
int st = -2e9, ed = -2e9;
for(auto i : q)
{
if(ed < i.first)
{
if(ed != -2e9) ans.push_back({st, ed});
st = i.first, ed = i.second;
}
else st = max(st, i.first), ed = min(ed, i.second);
}
if(ed != -2e9) ans.push_back({st, ed});
cout << ans.size();
return 0;
}
方法二 结构体贪心写法
1.算法细节
- 排序也可以重载小于号,不需要特判最后一个区间,代码更简洁
2.具体代码
左端点排序:类似区间合并
java
import java.util.*;
public class Main {
static int N = 100010, n;
static int edges[][] = new int [N][2];
public static void main(String [] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i=0; i<n; i++){
edges[i][0] = sc.nextInt();
edges[i][1] = sc.nextInt();
}
Arrays.sort(edges,0, n, (A, B) -> (A[0] - B[0]));
int l = edges[0][0];
int r = edges[0][1];
int res = 1;
for(int i=1; i<n; i++){
if(edges[i][0] > r){
res ++;
l = edges[i][0];
r = edges[i][1];
}
else r = Math.min(edges[i][1], r);
}
System.out.println(res);
}
}
python3
n = int(input())
edge = []
for i in range(n):
a, b = map(int, input().split())
edge.append([a, b])
# 左端点排序
edge.sort(key = lambda x: x[0])
res = 1
ed = edge[0][1]
for i in range(1, n):
if edge[i][0] > ed:
res += 1
ed = edge[i][1]
else:
ed = min(ed, edge[i][1])
print(res)
C++
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
struct seg{
int l, r;
}s[N];
bool cmp(seg a, seg b){
return a.l < b.l;
}
int main()
{
int n, res = 0, ed = -2e9, l, r;
cin >> n;
for(int i=0; i<n; i++)
{
cin >> l >> r;
s[i] = {l,r};
}
sort(s, s+n, cmp);
for(int i=0; i<n; i++)
{
if(s[i].l > ed)
{
res ++;
ed = s[i].r;
}
else ed = min(ed, s[i].r);
}
cout << res << endl;
return 0;
}
右端点排序: y总思路
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Seg
{
int l, r;
}s[N];
bool cmp(seg a, seg b)
{
return a.r < b.r;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &s[i].l, &s[i].r);
sort(s, s + n, cmp);
int res = 0, ed = -2e9;
for (int i = 0; i < n; i ++ )
if (s[i].l > ed)
{
res ++ ;
ed = s[i].r;
}
printf("%d\n", res);
return 0;
}