Sự cố khi tính phạm vi ngày trùng lặp

Question

Tôi gặp sự cố khi cố gắng tìm ra thuật toán chính xác để tính toán tập hợp các phạm vi ngày. Về cơ bản tôi có một danh sách các phạm vi ngày không theo thứ tự (Danh sách chứa các mảng thời gian bắt đầu và kết thúc) và tôi muốn hợp nhất danh sách này để nó không chứa thời gian trùng lặp.

Về cơ bản để củng cố hai phạm vi ngày:

if start1 <= end2 and start2 <= end1 //Indicates overlap 
    if start2 < start1 //put the smallest time in start1 
     start1 = start2 
    endif 
    if end2 > end1 //put the highest time in end1 
     end1 = end2 
    endif 
endif 

này tham gia hai lần ngày.

Tôi nhấn một trở ngại khi nói đến việc lặp qua tất cả các giá trị để danh sách kết thúc chỉ chứa các giá trị không chồng chéo.

Lập trình chức năng và đệ quy của tôi hơi bị gỉ và mọi trợ giúp đều được hoan nghênh.

Answer 1

Không nhìn vào các khoảng thời gian, chỉ nhìn vào đầu của chúng.

Bạn có một loạt các khoảnh khắc bắt đầu và một loạt các khoảnh khắc kết thúc. Hãy tưởng tượng rằng những khoảnh khắc bắt đầu là những khoảnh khắc màu đỏ và kết thúc có màu xanh dương. Hoặc tưởng tượng rằng những khoảnh khắc bắt đầu đang mở niềng răng và những khoảnh khắc kết thúc đang đóng niềng răng.

Đặt tất cả chúng lại với nhau trong một danh sách. Sắp xếp danh sách từ sớm nhất đến mới nhất, bỏ qua màu sắc.

Bây giờ hãy đặt bộ đếm bằng không với bạn và đi xuống danh sách. Khi bạn nhìn thấy một khoảnh khắc màu đỏ, tăng bộ đếm. Khi bạn thấy một khoảnh khắc màu xanh, hãy giảm bộ đếm. Khi giá trị bộ đếm đi từ 0 đến 1, đầu ra "bắt đầu" và thời gian hiện tại. Khi giá trị bộ đếm đi từ 1 đến 0, đầu ra "kết thúc" và thời gian hiện tại. Nếu giá trị truy cập giảm xuống dưới 0, đầu ra "Houston, chúng tôi có một vấn đề". Bạn nên kết thúc với bộ đếm của bạn tại 0 và một loạt các khoảng thời gian không chồng chéo đẹp.

Đây là thuật toán đếm cú đúp cũ tốt.

Minh họa.

A bunch of overlapping intervals: 

(-------------------) 
         (----------------------)   
                  (---) 
     (---------------------)      
                (-----------------) 

A bunch of interval ends: 

(-----(-------------)-(-----)----------------)  (----(---)--------) 

Answer 2

câu trả lời là tất cả những gì bạn cần nhưng nếu bạn muốn sử dụng mã bạn đã tạo thì chỉ cần sắp xếp phạm vi theo thời gian bắt đầu và đi qua danh sách trùng lặp.