Bài toán tính thời gian... bể bơi

[minhlyit]

mọi người giúp mình với!
đề bài là: 1 bể bơi mở cửa từ 5h-12h
xd thuật toán tìm xem trong khonảg tg nào bể bơi ko có người ( tức là trong khoảng 5h->12h)
mọi người cho mình ý tưởng để giải quyết bà toán này nha. Càng nhiều càng tốt
(^_^)!
Thanks mọi người nhìu

[ptaminh]

Khi một người x vào bể bơi, ta có thời điểm xi. Khi người đó ra ta có thời điểm xo.

Ứng với 1 khách hàng ta xác định được khoảng thời gian của người đó trong bể bơi là Tx = [xi,xo];

Ban đầu tập thời gian DT=[5,12].

Khi một người Xi nào đó ra(Xi đã vào trước đó). cập nhật lại DT = DT \ TXi

\ là phép trừ của tập hợp.

Đến lúc 12h kiểm tra xem DT còn lại là bao nhiêu. Tập hợp các khoảng thời gian còn lại chính là khoảng thời gian hồ bơi không có người.