今年暑假不AC

Problem Description

“今年暑假不AC？”
“是的。”
“那你干什么呢？”
“看世界杯呀，笨蛋！”
“@#$%^&*%...”

確實如此，世界杯來了，球迷的節日也來了，估計很多ACMer也會拋開電腦，奔向電視了。
作為球迷，一定想看盡量多的完整的比賽，當然，作為新時代的好青年，你一定還會看一些其它的節目，比如新聞聯播（永遠不要忘記關心國家大事）、非常6+7、超級女生，以及王小丫的《開心辭典》等等，假設你已經知道了所有你喜歡看的電視節目的轉播時間表，你會合理安排嗎？（目標是能看盡量多的完整節目）

?

?

Input

輸入數據包含多個測試實例，每個測試實例的第一行只有一個整數n(n<=100)，表示你喜歡看的節目的總數，然后是n行數據，每行包括兩個數據Ti_s,Ti_e (1<=i<=n)，分別表示第i個節目的開始和結束時間，為了簡化問題，每個時間都用一個正整數表示。n=0表示輸入結束，不做處理。

?

?

Output

對于每個測試實例，輸出能完整看到的電視節目的個數，每個測試實例的輸出占一行。

?

?

Sample Input

12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0

?

?

Sample Output

5

?

正確算法：

import java.util.Scanner;/*** 這個題目就是貪心算法，題目給出了節目的開始和結束時間，要使得能看盡量多的節目，那么關鍵就在于結束時間，所以需要將結束時間進行升序(對應的開始時間也要變化)，然后從第一個元素開始，比較第一個元素結束時間是否小于等于第二個元素的開始時間，如果符合，則節目數量加1。接著比較第二個元素的結束時間是否小于等于第三個元素的開始時間，依次循環。如果不符合，則比較第一個元素結束時間是否小于等于第三個元素的開始時間，依次循環。*/
public class 今年暑假不AC {public static void sort(int start[], int end[]) {for (int i = 0; i < end.length - 1; i++) {for (int j = 0; j < end.length - 1 - i; j++) {if (end[j] > end[j + 1]) {int tmp = end[j];end[j] = end[j + 1];end[j + 1] = tmp;int tmp2 = start[j];start[j] = start[j + 1];start[j + 1] = tmp2;}}}}public static void main(String[] args) {Scanner input = new Scanner(System.in);while (input.hasNext()) {int n = input.nextInt();if (n == 0) {break;}int[] start = new int[n];int[] end = new int[n];for (int i = 0; i < n; i++) {start[i] = input.nextInt();end[i] = input.nextInt();}sort(start, end);
//            for (int i = 0; i < start.length; i++) {
//                System.out.print(start[i] + " ");
//            }
//            System.out.println();
//            for (int i = 0; i < end.length; i++) {
//                System.out.print(end[i] + " ");
//            }
//            System.out.println();int count=1;int tmp=end[0];
//            System.out.println(start[0]+" "+end[0]);for (int i = 1; i < start.length; i++) {if(tmp<=start[i]){tmp=end[i];count++;
//                    System.out.println(start[i]+" "+end[i]);
                }}System.out.println(count);}}}

?