贪心法的应用(2) 区间交集问题

怼烎@ 2022-03-27 02:12 196阅读 0赞

### 问题描述: ###

给出N个开区间(X,Y),从中选择尽可能多的开区间,使得这些开区间两两之间没有交集

例如对开区间(1,3),(2,4),(3,5),(6,7)来说,可以选出最多3个区间(1,3),(3,5),(6,7)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70][]

思路:

首先对区间进行排序,将x较小的区间排在前面,因为如图a所示,区间越小,所能容纳的空间就越大

排序完成后,从最小的区间的下一区间开始,依次比较下一区间的x是否大于上一区间的y,如果成立,则说明它们不相交

然后把下一区间设置为当前区间,依次与接下来的区间比较,观察是否相交即可。

#include <iostream>
    #include <algorithm>
    #include <string>
    #include <string.h>
    using namespace std;
    struct Interval
    {
    	int x, y;
    }Intervals[1001];
    bool cmp(Interval a, Interval b) {
    	if (a.x != b.x) return a.x < b.x;
    	else return a.y < b.y;
    }
    int main() {
    	int n;
    	scanf("%d", &n);
    	for (int i = 0; i < n; ++i) {
    		scanf("%d %d", &Intervals[i].x, &Intervals[i].y);
    	}
    	int ans = 1;
    	int lastY = Intervals[0].y;
    	for (int i = 1; i < n; ++i) {
    		if (Intervals[i].x >= lastY) {
    			lastY = Intervals[i].y;
    			ans++;
    		}
    	}
    	printf("%d", ans);
    	system("PAUSE");
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FsZXgxOTk3MjIy_size_16_color_FFFFFF_t_70]: /images/20220327/350cb6bde56b4184b28fec46c49f8175.png

发表评论取消回复

表情：

评论列表（有 0 条评论，196人围观）

还没有评论，来说两句吧...

相关阅读

相关区间贪心算法-——活动安排问题

问题题目设有n个活动的集合E=\{1,2,…,n\}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用

﹏ヽ暗。殇╰゛Y/ 2023年10月05日 15:58/ 0 赞/ 4 阅读

相关区间覆盖（贪心）

题目描述给定N个闭区间\[ai,bi\]以及一个线段区间\[s,t\]，请你选择尽量少的区间，将指定线段区间完全覆盖。输出最少区间数，如果无法完全覆盖则输出-1。

旧城等待，/ 2022年10月25日 14:25/ 0 赞/ 163 阅读

相关 986. 区间列表的交集

给定两个由一些闭区间组成的列表，firstList 和 secondList ，其中 firstList\[i\] = \[starti, endi\] 而 secondL

末蓝、/ 2022年09月02日 05:20/ 0 赞/ 86 阅读

相关贪心算法之区间图着色问题

CLRS 16.1-3 假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有的活动。请给出一个有效的贪心算法，来确定哪一个活动应使用哪一个教室。 (这个

深碍√TFBOYSˉ_/ 2022年07月21日 00:09/ 0 赞/ 190 阅读

相关 C语言贪心区间覆盖问题

区间覆盖问题 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Problem D

女爷i/ 2022年06月01日 08:08/ 0 赞/ 173 阅读

相关贪心--HDU2037--不相交区间问题

不相交区间问题题目大意：小墨喜欢看电视，他会事先查看喜欢看得电视节目的转播时间，然后合理安排，以看到尽量多的完整节目。输入格式：输入多个实例，每个实例的第一行

不念不忘少年蓝@/ 2022年05月24日 04:07/ 0 赞/ 132 阅读

相关贪心算法——区间覆盖问题

区间覆盖问题数轴上有n个闭区间\[ai,bi\]，选择尽量少的区间覆盖一条指定的线段\[s,t\]。分析：把各区间按照a从小到大排序。如果

爱被打了一巴掌/ 2022年05月09日 07:08/ 0 赞/ 351 阅读

相关贪心算法——区间选点问题

转载：[https://blog.csdn.net/xia842655187/article/details/51944763][https_blog.csdn.net_xia

曾经终败给现在/ 2022年05月09日 07:08/ 0 赞/ 158 阅读

相关贪心算法区间问题——选择不想交区间

选择不想交的区间。数轴上有n个区间（ai,bi）。选择尽可能多个区间，使得这些区间没有公共点。分析：首先明确一个问题：假设有两个区间x,y，区间

た入场券/ 2022年05月09日 07:04/ 0 赞/ 227 阅读

相关贪心法的应用(2) 区间交集问题

问题描述: 给出N个开区间(X,Y),从中选择尽可能多的开区间,使得这些开区间两两之间没有交集例如对开区间(1,3),(2,4),(3,5),(6,7)来说,可以选出

怼烎@/ 2022年03月27日 02:12/ 0 赞/ 197 阅读