java - 算法问题：同一时间不能存在三个公告

Question

1.创建公告时有生效的时间段：开始时间和过期时间；

2.当创建新的公告时，要保证同一时间点不能存在三个同时生效的公告

Answer 1

每次新建的時候驗證，先查出與當前新建的有交叉的集合，然後驗證集合中有沒有兩兩交叉的，如果有，那麼就會不能創建，這樣就保證了不會在同一時間存在三個公告

Answer 2

直接寫個 sql 就搞定了：

select count(1) from table where start <= 新公告end and end >= 新公告start

如果結果小於3，就創建。

Answer 3

插入時，遍歷表，判斷當前時間戳是否在兩個時間戳之間，並記錄符合該條件的數量，若＞=3，不執行插入。否則，插入資料表。

Answer 4

用兩個時間點，統計一下這個時段裡面有效的公告有幾個！
多餘3個就不能創建了。

Answer 5

一個笨辦法，查出所有時間上與新公告有交集的，然後按日做統計

Answer 6

試著寫了下，可以參考一下，

public class OtherTest {
    public static void main(String[] args) {

        boolean bn = new OtherTest().test();
        System.out.println(bn);
    }
    public boolean test(){
        //查询出在要添加的公告时间段内的公告时间段
        TimeNode node1 =new TimeNode(1, 4);
        TimeNode node2 =new TimeNode(1, 4);
        TimeNode node3 =new TimeNode(9, 11);
        List<TimeNode> list= new ArrayList<TimeNode>();
        list.add(node1);
        list.add(node2);
        list.add(node3);
        //是否有交集？
        boolean insert = true;
        for(int i=0;i<list.size();i++){
            TimeNode nodeI = list.get(i);
            for(int j=(i+1);j<list.size();j++){
                TimeNode nodeJ = list.get(j);
                //如果存在两个时间段有交集 那说明在交集的时间段内已经有2个公告了，不能在添加了
                if(nodeI.end > nodeJ.start && nodeI.start < nodeJ.end){
                        insert = false; //false return
                        break;
                }
            }
            if(!insert){
                break;
            }
        }
        return insert;
    }
    
    class TimeNode{
        int start;
        int end;
        public TimeNode(int pStart,int pEnd){
            start = pStart;
            end = pEnd;
        }
    }
}

Answer 7

經典線段覆蓋問題。不會 Java，給你個 O(n) 的思路。

1. 先找出所有和待驗證區間有交集的區間，按區間左端點從小到大排序

2. 記第一個區間為 CurrentInternal

3. 對於 CurrentInternal，考察其下一項 NextInterval：若不與 CurrentInternal 相交，記其為 CurrentInternal，跳至 2；否則，記其交區間為 Intersection。

4. 對於 Intersection，遍歷 NextInterval 之後的項：若無與 Intersection 相交的區間，則記 NextInterval 為 CurrentInterval，跳至 2；否則，說明有三個相交的區間，退出。

5. 若遍歷完整個列表，則證明待驗證區間合法。

---

附上一個 JS 寫的 DEMO，希望大家玩得開心

https://jsfiddle.net/hsfzxjy/7td0rwr2/28/