PTIT127C spoj ptit- Bố trí phòng họp

Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT127C/

1. Đề bài PTIT127C spoj

Có n cuộc họp đánh số từ 1 đến n đăng ký làm việc tại một phòng hội thảo. Cuộc họp i cần được bắt đầu ngay sau thời điểm sivà kết thúc tại thời điểm f­i. Hỏi có thể bố trí phòng hội thảo phục vụ được nhiều nhất bao nhiêu cuộc họp, sao cho khoảng thời gian làm việc của hai cuộc họp bất kỳ là không giao nhau.

Input

  • Dòng đầu tiên chứa số nguyên dương n ( n <= 10000)
  • Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên dương si, fi (si < fi <= 32000) ( 1 <= i <= n).

Output

  • Dòng đầu tiên ghi số K là số các cuộc họp được chấp nhận phục vụ

2. Gợi ý PTIT127C spoj

– Các bạn dùng sắp xếp theo chiều tăng dần của B[i] (1<=i<=N) rồi dùng thuật toán tham lam tìm dãy cuộc hợp từ 1..i thỏa mãm B[i]>A[i]>=B[1..i-1].

3. Code tham khảo PTIT127C spoj Pascal

Code 1

 

Code 2

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *