Tìm khoảng thời gian tiểu học trong khoảng thời gian chồng chéo

Question

Tôi đã xem qua một câu hỏi hay trong khi chuẩn bị cho một số cuộc phỏng vấn lập trình.

Cho một tập hợp các khoảng thời gian có thể chồng chéo, bạn cần phải viết một hàm để trả về tất cả các khoảng thời gian chính giữa chúng. Ví dụ: nếu bạn được cung cấp khoảng thời gian như danh sách các cặp sau: {{1,5}, {3,10}, {5,11}, {15,18}, {16,20}}, thì bạn cần để trả lại những điều sau:

{{1,3}, {3,5}, {5,10}, {10,11}, {15,16}, {16,18}, {18,20 }}

Lưu ý những điều sau trong câu trả lời ở trên:

• khoảng {11,15} được bỏ qua trong các câu trả lời vì nó là không tồn tại trong đầu vào.
• Khoảng cách {1,5} từ đầu vào đã được chia thành {1,3}, {3,5} trong câu trả lời vì điểm bắt đầu "3" được xác định trong {3,10} trong đầu vào cắt khoảng thời gian thành hai khoảng thời gian tiểu học.

Phương pháp chữ ký trong Java:

List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer> intervals) 

Một trong những giải pháp mà tôi tưởng tượng là để tách các đầu vào thành các tập không giao nhau, và sau đó một O đơn giản (NlogN) loại trên tất cả các số trong mỗi bộ không giao nhau sẽ mang lại câu trả lời. Có cách nào hiệu quả hơn để làm điều đó không?

Answer 1

Bạn có thể phá vỡ vấn đề này lên vào khoảng lồng đầu tiên, sau đó đối phó với mỗi lồng riêng biệt. Bởi lồng nhau, tôi có nghĩa là khoảng thời gian chia sẻ ít nhất một điểm.Đối với ví dụ bạn đưa ra:

{{1,5}, {3,10}, {5,11}, {15,18}, {16,20}} 

có hai nestings:

{1,5}, {3,10}, {5,11} 

và

{15,18}, {16,20} 

Nói chung, để xác định nestings, bạn có thể sắp xếp các khoảng thời gian dựa trên bên trái điểm cuối (như trong ví dụ của bạn), sau đó chạy qua và bắt đầu một tổ mới bất cứ khi nào bạn thấy {x,y}, {x',y'} với y < x'.

Để lồng ghép, "khoảng thời gian cơ bản" được tạo thành bởi chuỗi được sắp xếp (không lặp lại) các giá trị. Trong ví dụ này, các nestings cho

(1,3,5,10,11) -> {1,3}, {3,5}, {5,10}, {10,11} 

và

(15,16,18,20) -> {15,16}, {16,18}, {18,20} 

Vì vậy, các thuật toán tổng thể có thể trông như thế này:

• Sắp xếp các khoảng dựa trên thiết bị đầu cuối bên trái
• Chạy qua khoảng thời gian cho đến {x,y}, {x',y'} với y < x'
• Fr om bắt đầu {x,y}, làm cho danh sách được sắp xếp thiết bị đầu cuối (không lặp lại), nói a0,a1,...,ak
• Thêm khoảng tiểu {ai,a(i+1)} cho i = 0...k-1
• Di chuyển khoảng lên đến {x,y} và tiếp tục từ bước 2

Answer 2

Thuật toán đơn giản là chỉ cần đọc qua toàn bộ danh sách các số và tạo thành phần cho mỗi mục trong mỗi cặp.

Mỗi phần tử sẽ lưu trữ hai giá trị: number và cho dù đó là số đầu tiên hay số thứ hai (từ đầu vào).

Những cặp sau đó sẽ được sắp xếp, trước hết bởi nội number của nó, và sau đó bởi vị trí của nó (second sẽ đi trước first)

Để in ra danh sách các khoảng thời gian, bạn sẽ in mỗi số cùng với tiếp theo số, với các quy tắc sau:

• bạn sẽ không in số lặp đi lặp lại (ví dụ như vậy, bạn sẽ không in 5,5)
• Nếu bạn hoàn toàn có một số second, và sau đó một first số, bạn sẽ không in khoảng thời gian tiểu học đó, vì không có giá trị nào trong phạm vi đó.

Answer 3

Bạn có thể sắp xếp các điểm cuối và sau đó lặp lại theo thứ tự. Để biết bạn đang ở trong hay ngoài, bạn có thể giữ số khoảng thời gian bao trùm từng điểm. Sự kết thúc trái của khoảng thời gian góp phần 1, trong khi bên phải góp phần -1: (Lưu ý rằng tôi sử dụng TreeMap, được sắp xếp)

static class Pair<T, K> { 
    public Pair(T first, K second){ 
     this.first = first; 
     this.second = second; 
    } 

    public String toString(){ 
     return "(" + first + ", " + second + ")"; 
    } 

    T first; 
    K second; 
}  

static List<Pair<Integer, Integer>> generateElementaryIntervals(List<Pair<Integer, Integer>> intervals) { 
    TreeMap<Integer, Integer> overlaps = new TreeMap<Integer, Integer>(); 
    for(Pair<Integer, Integer> interval : intervals){ 
     int value = overlaps.containsKey(interval.first) ? overlaps.get(interval.first)+1 : 1; 
     overlaps.put(interval.first, value); 

     value = overlaps.containsKey(interval.second) ? overlaps.get(interval.second)-1 : -1; 
     overlaps.put(interval.second, value); 
    } 

    List<Pair<Integer, Integer>> retValue = new ArrayList<Pair<Integer,Integer>>(); 

    int overlap = 0; 
    boolean in = false; 
    int last = 0; 
    for(int point : overlaps.keySet()){ 
     if(in) 
      retValue.add(new Pair(last, point)); 

     overlap += overlaps.get(point); 
     last = point; 
     in = overlap > 0; 
    } 

    return retValue; 
}  

public static void main(String[] args) { 

    List<Pair<Integer, Integer>> l = new ArrayList<Pair<Integer, Integer>>(); 
    l.add(new Pair<Integer, Integer>(1,5)); 
    l.add(new Pair<Integer, Integer>(3,10)); 
    l.add(new Pair<Integer, Integer>(5,11)); 
    l.add(new Pair<Integer, Integer>(15,18)); 
    l.add(new Pair<Integer, Integer>(16,20)); 

    for(Object o : generateElementaryIntervals(l)){ 
     System.out.println(o.toString()); 
    } 

}