会场安排问题
时间限制:3000 ms | 内存限制:65535 KB
难度:4
每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。
随后的n行,每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间(Bi<=Ei)
每组的输出占一行
2 2 1 10 10 11 3 1 10 10 11 11 20
1 2
import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scannner = new Scanner(System.in); int m, n; m = scannner.nextInt(); for (int i = 0; i < m; i++) { n = scannner.nextInt(); List<Hui> list = new ArrayList<Hui>(); for (int j = 0; j < n; j++) { Hui hui = new Hui(); hui.start = scannner.nextInt(); hui.end = scannner.nextInt(); list.add(hui); } Collections.sort(list, new sort()); int num = 1; int end = list.get(0).end; for(int k=1;k<n;k++){ if(list.get(k).start>end){ end = list.get(k).end; num++; } } System.out.println(num); } } } class sort implements Comparator<Hui>{ @Override public int compare(Hui o1, Hui o2) { return o1.end.compareTo(o2.end); } } class Hui { public Integer start; public Integer end; }
#include<iostream> #include<fstream> #include<vector> #include<algorithm> using namespace std; struct activ { int begin; int end; }; bool cmp(activ a,activ b) { return a.end<b.end; } int main() { ifstream cin("input.txt"); int n; cin>>n; while (n--) { int i,m; cin>>m; vector<activ> vec; for(i=0;i<m;i++) { activ a; cin>>a.begin>>a.end; vec.push_back(a); } sort(vec.begin(),vec.end(),cmp); int count=vec.size(); int k=0; for (i=1;i<vec.size();i++) { if(vec[i].begin <= vec[k].end) count--; else k=i; } cout<<count; } return 0; }
相关推荐
用贪心算法解决会场按排问题,用netbeans6.8做的。已经编译通过没任何错误,JAVA 源文件。
会场安排问题就是一种典型的贪心算法应用实例。 在会场安排问题中,我们通常面临这样的场景:有多个会议需要在一个有限的会场里进行,每个会议都有其开始和结束时间,并且要求一个会场在同一时间内只能安排一个会议...
### 活动安排问题与贪心算法 #### 一、问题背景与定义 在活动安排问题中,我们面临的情况是需要在一个或多个会场安排一系列活动,目标是最小化所需的会场数量。该问题可以被视为一个图着色问题:如果我们将每个...
贪心算法在会场安排问题中的应用 贪心算法是一种常用的算法设计方法, especialmente 在解决组合优化问题时。贪心算法的基本思想是, 在每一步都选择当前最优的解决方案,并且希望通过这种方式来达到最优的解。贪心...
会议安排问题(贪心算法) VC下调试OK
设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于...
多会场安排问题的贪心算法有很多实际应用,例如会议室安排、班车安排、机器安排等。在这些应用中,我们都需要将活动安排到最少的会场上,以提高资源利用率和降低成本。 多会场安排问题的贪心算法是一种effective的...
贪心法求解会场安排问题 & 基于分治法的循环日程表算法 本实验 Report 涉及到两种算法,分别是贪心法和分治法,用于解决会场安排问题和循环日程表问题。 一、贪心法求解会场安排问题 1. 问题描述:在有 n 个会议...
【活动安排问题(贪心算法)报告】 活动安排问题是一个典型的优化问题,旨在在一个资源有限的情况下,找到最多相容的活动子集。在这个问题中,每个活动都有一个开始时间和结束时间,同一时间只能进行一个活动。贪心...
本文将详细探讨如何使用C++语言解决“会场安排问题”,这是在软件开发中常见的一个优化问题,尤其在资源调度和管理领域有着广泛的应用。我们将深入理解问题背景,学习相关算法,并通过在Visual Studio环境下编写和...
贪心算法会场安排问题算法设计分析 贪心算法会场安排问题算法设计分析是对图着色问题的一种解决方案,旨在使用尽可能少的会场来安排一批活动。该问题的核心思想是将每一个活动作为图的一个顶点,不相容活动间用边...
### 会场安排问题算法设计 #### 问题背景与目标 在实际生活中,经常会遇到需要在多个会场中安排各种活动的情况。为了提高资源利用效率,我们希望能够使用尽可能少的会场来完成所有活动的安排。这实际上是一个经典...
### 贪心算法在会场安排问题中的应用 #### 一、问题背景与定义 在现实生活中,经常需要在多个会场之间合理地安排不同的活动。为了提高资源利用效率,我们希望用尽可能少的会场来安排这些活动。本问题就是基于这样...
贪心算法(会场安排)源代码.txt
会场安排问题 超实用简洁 算法设计与分析 贪心法解决
1.贪心算法解决问题的策略是只考虑眼前情况。2.由题目可知会议需要按时举行,并且会场使用个数最少,即尽可能的提高会场的利用率。3.策略为:将会议按开始时间顺序进行排序,同时记录所使用的会场的结束时间,如果...
假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。 用C++语言实现
设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于...
### 会场问题的贪心算法 #### 一、问题背景与定义 在计算机科学与算法设计领域,会场问题是常见的资源分配问题之一。该问题通常可以表述为:有一系列会议需要安排在有限数量的会场中进行,每个会议都有其特定的...