当前位置:编程学习 > JAVA >>

java--会场安排问题

描述
学校的小礼堂每天都会有许多活动,有时间这些活动的计划时间会发生冲突,需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动,每个时间最多安排一个活动。现在小刘有一些活动计划的时间表,他想尽可能的安排更多的活动,请问他该如何安排。

输入
第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数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提示
注意:如果上一个活动在t时间结束,下一个活动最早应该在t+1时间开始


这里提供一种利用jdk中PriorityQueue,一个基于优先级堆的无界优先级队列。

 

 

[java]
import java.util.PriorityQueue; 
import java.util.Scanner; 
 
public class Main { 
 
    public static Scanner sc = new Scanner(System.in); 
 
    public static void main(String[] args) { 
 
        int n = Integer.parseInt(sc.nextLine());// n=2  
 
        while (n-- > 0) { 
 
            int num = Integer.parseInt(sc.nextLine());// num表示有几个活动2  
            //一个基于优先级堆的无界优先级队列。  
            PriorityQueue<MeetingTime> queue = new PriorityQueue<MeetingTime>(); 
 
            for (int i = 0; i < num; i++) { 
                String[] activitys = sc.nextLine().split(" "); 
                MeetingTime activity = new MeetingTime( 
                        Integer.parseInt(activitys[0]), Integer 
                                .parseInt(activitys[1])); 
 
                queue.add(activity); 
            } 
 
            int count = 1;//最少是一个活动  
            // 取出第一个活动  
            int endTime = queue.poll().endTime; 
            for (int i = 1; i < num; i++) { 
                if(endTime < queue.peek().beginTime){ 
                    //说明存在  
                    count ++; 
                    endTime = queue.peek().endTime; 
                } 
                queue.poll();//获取并移除此队列的头,  
            } 
             
            queue.clear(); 
             
            System.out.println(count); 
        } 
    } 

 
class MeetingTime implements Comparable<MeetingTime>{ 
 
    int beginTime; 
    int endTime; 
 
    public MeetingTime(int beginTime, int endTime) { 
        this.beginTime = beginTime; 
        this.endTime = endTime; 
    } 
 
    @Override 
    public int compareTo(MeetingTime o) { 
        if(this.endTime > o.endTime){ 
            return 1; 
        }else{ 
            return -1; 
        } 
    } 
 
     
 

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

 public static Scanner sc = new Scanner(System.in);

 public static void main(String[] args) {

  int n = Integer.parseInt(sc.nextLine());// n=2

  while (n-- > 0) {

   int num = Integer.parseInt(sc.nextLine());// num表示有几个活动2
   //一个基于优先级堆的无界优先级队列。
   PriorityQueue<MeetingTime> queue = new PriorityQueue<MeetingTime>();

   for (int i = 0; i < num; i++) {
    String[] activitys = sc.nextLine().split(" ");
    MeetingTime activity = new MeetingTime(
      Integer.parseInt(activitys[0]), Integer
        .parseInt(activitys[1]));

    queue.add(activity);
   }

   int count = 1;//最少是一个活动
   // 取出第一个活动
   int endTime = queue.poll().endTime;
   for (int i = 1; i < num; i++) {
    if(endTime < queue.peek().beginTime){
     //说明存在
     count ++;
     endTime = queue.peek().endTime;
    }
    queue.poll();//获取并移除此队列的头,
   }
   
   queue.clear();
   
   System.out.println(count);
  }
 }
}

class MeetingTime implements Comparable<MeetingTime>{

 int beginTime;
 int endTime;

 public MeetingTime(int beginTime, int endTime) {
  this.beginTime = beginTime;
  this.endTime = endT

补充:软件开发 , Java ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,