8602 区间相交问题(必做)
时间限制:1000MS 内存限制:1000K
提交次数:1966 通过次数:468
题型: 编程题 语言: C++;C;VC;JAVA
Description
给定x轴上n个闭区间,去掉尽可能少的闭区间,使剩下的闭区间都不相交。
注意:这里,若区间与另一区间之间仅有端点是相同的,不算做区间相交。例如,[1,2]和[2,3]算是不相交区间。
输入格式
第一行一个正整数n(n<=50),表示闭区间数。接下来n行中,每行2个整数,表示闭区间的2个整数端点。
输出格式
输出去掉的最少的闭区间数。
输入样例
3
10 20
10 15
12 15
输出样例
2
这个问题基本等同于书本的活动安排问题。
网上的一种用了pair,所以写得有点恶心。记住 second 是左端点, first 才是右端点就行了。
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
pair<int,int> p[n];
for(int i=0; i<n; i++)
{
cin >> p[i].second;
cin >> p[i].first;
if(p[i].second > p[i].first)
{
swap(p[i].second, p[i].first);
}
}
sort(p, p+n);
int last, cnt;
last = p[0].first;
cnt = 1;
for(int i=1; i<n; i++)
{
if(p[i].second >= last)
{
cnt++;
last = p[i].first;
}
}
cout << n - cnt << endl;
}
return 0;
}
第二种:
#include <iostream>
#include <string.h>
#include <algorithm>//c++ sort
using namespace std;
int cmp( const int &a, const int &b ){
if( a > b )
return 1;
else
return 0;
}// sort(a,a+n,cmp);
struct Extent
{
int a,b;
bool operator < (const Extent& S)const
{
return b < S.b;
}
}B[10002];
int main()
{
int s[100];
int f[100];
int n,m;
cin >>n;
m=n;
for(int i=1;m>0;i++,m--){
cin >>B[i].a;
cin >>B[i].b;
}
sort(B,B+n);
// int A[100];
// memset(A,0,100*sizeof(int));
int sum=0;
int end = -1;
for(int i=1;i<=n;i++){
if(end<=B[i].a){
end=B[i].b;
sum++;
}
}
cout << n-sum << endl;
return 0;
}
第三种:#include <iostream>
#include <stdio.h>
using namespace std;
int n;
int s[100];
int e[100];
void myS(){
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
if(e[i]>e[j]){ //注意是比较结束时间
int temp = s[i];
s[i] = s[j];
s[j] = temp;
temp = e[i];
e[i] = e[j];
e[j] = temp;
}
}
}
}
int main()
{
freopen("in.txt","r",stdin);
cin >> n;
for(int i=0;i<n;i++)
cin >> s[i] >> e[i];
myS();
int num =1; // 注意num 至少为1
int ee = e[0]; //假定第一个为标准
for(int i=1;i<n;i++){
if(ee<=s[i]){ //注意是>= 边界问题
num++;
ee = e[i];
}
}
cout << n-num << endl;
return 0;
}
相关推荐
注意:这里 若区间与另一区间之间仅有端点是相同的 不算做区间相交 例如 [1 2]和[2 3]算是不相交区间 输入格式 第一行一个正整数n n< 50 表示闭区间数 接下来n行中 每行2个整数 表示闭区间的2个整数端点 ...
注意:这里,若区间与另一区间之间仅有端点是相同的,不算做区间相交。例如,[1,2]和[2,3]算是不相交区间。 输入格式 第一行一个正整数n,表示闭区间数。接下来n行中,每行2个整数,表示闭区间的2个整数端点。 ...
给定n个闭区间[ai, bi](1 ),这些区间的并可以表示为一些不相交的闭区间的并。要求在这些表示方式中找出包含不相交区间数目最少的方案。 【输入形式】 输入文件为当前目录下的prz.in。 该文件的第一行包含一个...
情形1:区间完全覆盖问题 情形2:最大不相交区间数问题 情形3:区间选点问题
已知 n 个左闭右开区间 [ a , b) ,对其进行 m 次询问,求区间 [ l , r ] 最多可以包含 n 个区间中的多少个区间,并且被包含的所有区间都不相交。 用于贪心算法对区间包含问题的解决
matlab 中连续区间进行交并集操作,输入输出为向量表示的连续区间如A=[a,b,c,d]表示A=(a,b)U(c,d),A为最简表达式,各个集合不相交
java java_leetcode面试题解哈希表第352题将数据流变为多个不相交区间_题解
1288. 删除被覆盖区间典型的区间覆盖问题# 1. 找到覆盖区间# 2. 找到相交区间,合并# 3. 完全不想交,更新起始点return len(interv
区间合并如果两个区间有交集,则将区间合并为一个区间与区间之间的关系分为三类:彼此互不相交后一个区间被前一个区间包含后一个区间与前一个有相交的部分// 将所有存在
21 最长k可重区间集问题 最大权不相交路径 最小费用最大流 22 最长k可重线段集问题 最大权不相交路径 最小费用最大流 23 火星探险问题 线性规划网络优化 最小费用最大流 24 骑士共存问题 二分图最大独立集 网络最小...
给定N个整数 A1,A2....AN组成序列。如果对于i,有Ak|Aj|,则称Aj覆盖序列区间Ai....Aj,相应的覆盖区间长度为j-i+1。最大覆盖问题就是求给定序列的最大覆盖区间长度!
例如,假设数据流中的整数为 1,3,7,2,6,…,每次的总结为:[1, 1], [3, 3], [7, 7]进阶:如果有很多合并,并且与数据流的大小相比,不相
例如,假设数据流中的整数为 1,3,7,2,6,…,每次的总结为:[1, 1], [3, 3], [7, 7]进阶:如果有很多合并,并且与数据流的大小相比,不相
- 选择不相交区间问题 & - 区间覆盖问题 & - 区间选点问题 & - 流水作业调度问题 & - 带期限和罚款的单位时间任务调度问题 五大贪心问题模板与解析。 适合人群: 普及晚期或提高早期的萌新 OIer 们。 ...
合并任务的一个简单的函数: 给定括号形式的 N 个输入闭区间: Ii := [left(i),...=N,所以分区是最小基数),并且{Jk} 彼此不相交(它们的交集是空的)。 此函数按升序返回 Jk = [lower(k),upper(k)], k=1,2,...M。
y=interval_union(x) 采用表示闭区间的 2 列矩阵,并且返回具有相同集合并集的不相交闭区间矩阵。 该算法通过将所有输入端点放在单个向量中、为左/右端点分配 +/-1 的“分数”并通过排序端点运行并通过 cumsum 累积...