題目描述
Being a fan of all cold-weather sports (especially those involving cows),Farmer John wants to record as much of the upcoming winter Moolympics as possible.
The television schedule for the Moolympics consists of N different programs(1 <= N <= 150), each with a designated starting time and ending time. FJ has a dual-tuner recorder that can record two programs simultaneously.
Please help him determine the maximum number of programs he can record in total.

農民約翰熱衷于所有寒冷天氣的運動（尤其是涉及到牛的運動）， 農民約翰想記錄盡可能多的moolympics為即將到來的冬季 可能的。 為moolympics電視時間表由N個不同的程序 （1 < = n＝150），每個具有指定的開始時間和結束時間。FJ 有一個雙調諧器錄音機，可以同時錄制兩個節目。 請幫助他確定他能錄制的節目的最大數量。

輸入輸出格式

輸入格式：
* Line 1: The integer N.
* Lines 2..1+N: Each line contains the start and end time of a single program (integers in the range 0..1,000,000,000).
第1行：整數n。 第2行.. 1 + n：每行包含單個的開始和結束時間 程序（范圍為0…1000000000的整數）。

輸出格式：
* Line 1: The maximum number of programs FJ can record.
僅一行，節目FJ可以記錄的最大數量。

輸入輸出樣例

輸入樣例#1：
6
0 3
6 7
3 10
1 5
2 8
1 9
輸出樣例#1：
4

說明
INPUT DETAILS:
The Moolympics broadcast consists of 6 programs. The first runs from time 0 to time 3, and so on.
OUTPUT DETAILS:
FJ can record at most 4 programs. For example, he can record programs 1 and 3 back-to-back on the first tuner, and programs 2 and 4 on the second tuner.
Source: USACO 2014 January Contest, Silver
.
.
.
.
.
.
.

分析

用貪心。
按照結束時間排序。
若節目可以放.則必定放。
盡量放在結束時間長的1組。
.
.
.
.
.
.

程序：

var a,b:array[0..151] of longint; i,j,n,t,t1,s:longint; beginreadln(n);for i:=1 to n doreadln(a[i],b[i]);for i:=1 to n-1 dofor j:=i+1 to n doif (b[i]>b[j]) or (b[i]=b[j]) and (a[i]>a[j]) thenbegint:=b[i];b[i]:=b[j];b[j]:=t;t:=a[i];a[i]:=a[j];a[j]:=t;end;t:=0;t1:=0;s:=0;for i:=1 to n doif a[i]>=t thenbegininc(s);if (t1>=t)and(a[i]>=t1) then t1:=b[i] else t:=b[i];end elseif a[i]>=t1 thenbegininc(s);t1:=b[i];end;writeln(s); end.

轉載于:https://www.cnblogs.com/YYC-0304/p/9499976.html

總結

以上是生活随笔為你收集整理的[USACO14JAN]记录奥林比克的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。