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

Question

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

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

Answer 1

Verify every time you create a new one. First find out the set that intersects with the currently created one, and then verify whether there are any two-by-two intersections in the set. If there is, then it will not be created, thus ensuring that they will not exist at the same time. Three announcements

Answer 2

Just write sql and it’s done:

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

If the result is less than 3, create it.

Answer 3

When inserting, traverse the table, determine whether the current timestamp is between two timestamps, and record the number that meets this condition. If >= 3, the insertion will not be performed. Otherwise, insert into the data table.

Answer 4

Use two time points to count how many effective announcements there are in this time period!
You cannot create more than 3 items.

Answer 5

A stupid way to find out all the times that overlap with new announcements, and then make statistics by day

Answer 6

I tried to write it down, you can refer to it,

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

Classic line segment coverage problem. I don’t know Java, so I’ll give you an O(n) idea.

1. First find all the intervals that intersect with the interval to be verified, Sort by the left endpoint of the interval from small to large

2. Remember the first interval as CurrentInternal

3. For CurrentInternal, examine its next item NextInterval: if it does not intersect with CurrentInternal, record it as CurrentInternal and jump to 2; otherwise, record its intersection interval as Intersection.

4. For Intersection, traverse the items after NextInterval: If there is no interval that intersects with Intersection, then record NextInterval as CurrentInterval and jump to 2; otherwise, it means there are three intersecting intervals and exit.

5. If the entire list is traversed, it proves that the interval to be verified is legal.

---

A DEMO written in JS is attached, I hope you all have fun

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