Đoạn rời 1

Đề Bài: 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 K đoạn thẳng không giao nhau. Hai đoạn thẳng [a,b] và [c,d] được coi là không giao nhau nếu xếp chúng trên cùng một trục số, chúng không có điểm chung. Điều kiện này đòi hỏi: b < c hoặc d < a.

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 < N £ 1000. Dòng thứ i trong N dòng tiếp theo, mỗi dòng chứa hai số nguyên ai bi cách nhau qua dấu cách, biểu thị điểm đầu và điểm cuối của đoạn thứ i, i = 1..N.  Dữ liệu ra: tệp văn bản DOAN.OUT Dòng đầu tiên: số tự nhiên K. K dòng tiếp theo, mỗi dòng một số tự nhiên v thể hiện chỉ số của các đoạn rời nhau tìm được. Thí dụ bên cho biết tối đa có 5 đoạn rời nhau là 1, 2, 7, 3 và 4.
8 2 3 4 5 10 12 13 15 1 9 2 5 6 8 7 15	5 1 2 7 3 4

Thuật toán

Phương pháp: tham.

1. Sắp các đoạn tăng theo đầu phải b.

2. Khởi trị: Lấy đoạn 1, đặt r = b₁ là đầu phải của đoạn này

3. Với mỗi đoạn j := 2..N tiếp theo xét:

Nếu đầu trái của đoạn j, a_j > r thì  lấy đoạn   j  đưa vào kết quả

và chỉnh r là đầu phải của đoạn j, r := b_j.

Độ phức tạp: cỡ NlogN  chi phí cho quick sort.

(*  Pascal  *)

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

  Doan roi 1: Liet ke toi da cac doan thang

              khong giao nhau

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

program DoanRoi1;

uses crt;

const mn = 1001; bl = #32 {Dấu cách}; nl = #13#10 {Xuống dòng};

      fn = 'doan.inp'; gn = 'doan.out';

type { Mô tả một đoạn }

  KieuDoan = record

               a,b: integer;

               id: integer; { Chỉ số đoạn }

             end;

  md1 = array[0..mn] of KieuDoan;

  mi1 = array[0..mn] of integer;

var n,m,r: integer; { n – số lượng đoạn }

                    { m – số lượng đoạn được chọn }

                    { r – đầu phải đang duyệt     }

    d: md1; { các đoạn d[1..n] }

    f,g: text;

    c: mi1; { mảng chứa kết qủa }

procedure Doc;

 var i: integer;

begin

  assign(f,fn); reset(f); readln(f,n);

  for i := 1 to n do

   begin

     read(f,d[i].a,d[i].b); d[i].id := i;

   end;

  close(f);

end;

(*---------------------------------

    Sắp tăng các đoạn d[t..p] theo

    đầu phải b.

  ---------------------------------*)

procedure Qsort(t,p: integer);

var i,j,m: integer;

    x: KieuDoan;

begin

  i := t; j := p; m := d[(i + j) div 2].b;

  while (i <= j) do

   begin

    while (d[i].b < m) do i := i + 1;

    while (m < d[j].b) do j := j - 1;

    if (i <= j) then

     begin

       x := d[i]; d[i] := d[j]; d[j] := x;

       i := i + 1; j := j - 1;

     end;

   end;

   if (t < j) then Qsort(t,j);

   if (i < p) then Qsort(i,p);

end;

procedure XuLi;

var i: integer;

begin

  m := 1; c[m] := 1; { Đưa đoạn 1 vào kết quả }

  r := d[m].b; { đầu phải của đoạn cuối trong kết quả }

  for i := 2 to n do

    if (r < d[i].a) then

      begin

        m := m + 1; c[m] := i; r := d[i].b;

      end;

end;

procedure Ghi;

  var i: integer;

begin

  assign(g,gn); rewrite(g); writeln(g,m);

  for i := 1 to m do writeln(g,d[c[i]].id);

  close(g);

end;

BEGIN

  Doc; Qsort(1,n); XuLi; Ghi;

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH