NKREZ - Hội trường - Solution for SPOJ

Problem

https://vn.spoj.com/problems/NKREZ

https://oj.vnoi.info/problem/NKREZ

Nhà trường có một phòng hội trường. Có những yêu cầu muốn sử dụng phòng hội trường này, mỗi yêu cầu cho biết thời điểm bắt đầu và thời điểm kết thúc. Nhà trường có thể chấp nhận hoặc từ chối đối với một yêu cầu.

Yêu cầu: hãy giúp nhà trường chọn các yêu cầu sử dụng hội trường sao cho tổng thời gian hội trường được sử dụng là lớn nhất.

Dữ liệu

Dòng đầu tiên chứa một số nguyên dương n (n ≤ 10000), số yêu cầu.

Mỗi dòng trong số n dòng tiếp theo chứa 2 số nguyên dương p và k (0 ≤ p < k ≤ 30000), mô tả một yêu cầu bắt đầu tại thời điểm p và kết thúc tại thời điểm k.

Kết qủa

Gồm một dòng duy nhất là tổng thời gian lớn nhất mà hội trường được sử dụng

Ví dụ

**Dữ liệu:**
12
2
5
4
8
13
6
10
12
14
19
16
20

**Kết qủa**
16

Tutorial

Sort tăng dần theo thời gian kết thúc. Tại yêu cầu thứ i, ta cần tìm thời gian cực đại trước lúc nó bắt đầu, tức là trước p[k].

Gọi F[i] là thời gian dùng nhiều nhất xét đến yêu cầu thứ i. Có hai khả năng, thứ nhất hủy yêu cầu này, tức là F[i-1], thứ hai dùng yêu cầu này, tức là tìm ra yêu cầu k nào đó có thời điểm kết thúc <= thời điểm bắt đầu của i, do tối ưu toàn bộ F[] trong suốt quá trình duyệt, nên F[i] = F[k] + thời gian làm việc của yêu cầu này. k thì chặt nhị phân tìm kiếm cơ bản

Nói thêm bài này còn một cách khác là dùng bit (xem thêm tại phần BIT) (thực tế bản chất hai cách là như nhau, chỉ khác chỗ người làm nhìn nhận vấn đề theo cách tính nào) (lúc đầu mình làm cách này, một năm sau mình bỗng nghĩ ra BIT ☺)

Submission

NKREZ.cpp

Tutorial SPOJ

NKREZ - Hội trường