会场安排问题
时间限制：
3000 ms | 内存限制：
65535 KB
难度：
4
描述
学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。
输入
第一行是一个整型数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
import java.util.Scanner;
public class Main {
private static void quickSort(int arr[][],int start,int end) {
if(start<end)
{
int low=start;
int high=end;
int temp1=arr[start][0];
int temp2=arr[start][1];
while(low<high)
{
while(low<high && arr[high][1]>=temp2)
{
high--;
}
arr[low][0]=arr[high][0];
arr[low][1]=arr[high][1];
while(low<high && arr[low][1]<=temp2)
{
low++;
}
arr[high][0]=arr[low][0];
arr[high][1]=arr[low][1];
}
arr[low][0]=temp1;
arr[low][1]=temp2;
quickSort(arr,start,low-1);
quickSort(arr,low+1,end);
}
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
while(n--!=0)
{
int m=scanner.nextInt();
int arr[][]=new int[m][2];
for(int i=0;i<m;i++)
{
for(int j=0;j<2;j++)
{
arr[i][j]=scanner.nextInt();
}
}
quickSort(arr,0,m-1);
/* for(int i=0;i<m;i++)
{
for(int j=0;j<2;j++)
{
System.out.print(arr[i][j]+" ");
}
System.out.println();
}
*/ int sum=1,start=0;
for(int i=1;i<m;i++)
{
if(arr[i][0]>arr[start][1])
{
start=i;
sum++;
}
}
System.out.println(sum);
}
}
}
转载请注明原文地址: https://ju.6miu.com/read-660117.html
