Đoạn rời 2

Cho N đoạn thẳng với các điểm đầu a_i và điểm cuối b_i là những số nguyên trong khoảng-1000..1000, a_i < b_i. Liệt kê số lượng tối đa các đoạn thẳng rời nhau. Hai đoạn được xem là rời nhau nếu chúng không có điểm chung. Các đoạn có dạng như trong bài Phủ đoạn 2.

DOAN.INP	DOAN.OUT		Dữ liệu vào: tệp văn bản DOAN.INP Dòng đầu tiên: số tự nhiên N > 1. Từ dòng thứ hai: liệt kê các đoạn, mỗi dòng có thể chứa nhiều đoạn, mỗi đoạn được ghi trọn trên một dòng. Dữ liệu ra: tệp văn bản DOAN.OUT Dòng đầu tiên: số  K. Tiếp theo là K số tự nhiên biểu thị chỉ số của các đoạn thẳng rời nhau.
8 ( -2, 3) [3 , 5) [8, 12] [13 ,15 ) (1 , 9 ) ( 2, 5 ]  [5 ,8 )  [7, 15]	5 1 2 7 3 4

Kết quả trên cho biết có tối đa 5 đoạn rời nhau là 1, 2, 7, 3 và 4.

Thuật toán

Phương pháp: Tham.

Trước hết ta chỉnh lại các đầu hở giống như bài trước sau đó áp dụng thuật toán của bài đoạn rời.

Các điểm đầu và cuối đoạn và các biến liên quan được khai báo kiểu số thực.

Độ phức tạp: N.logN  chi phí cho quick sort.

(*   Pascal   *)

(*========================================

   liet ke toi da cac doan thang roi nhau           

  =========================================*)

program DoanRoi2;

uses crt;

Tổ chức dữ liệu: xem bài Phủ đoạn 2

function DocSo: xem bai Phu doan 2;

procedure DocDoan: xem bai Phu doan 2;

procedure Doc: xem bai Phu doan 2;

procedure Qsort(l,r: integer): xem bai Phu doan 2;

procedure XuLi : xem bai Doan roi 1;

procedure Ket: xem bai Doan roi 1 ;

BEGIN

  Doc;   Qsort(1,n);

  XuLi;  Ket;

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH