求区间段覆盖总长度

喜欢ヅ旅行 2024-02-18 19:32 80阅读 0赞

### 问题 ###

现有一直线，从原点到无穷大。  
这条直线上有N个线段。线段可能相交。  
问，N个线段总共覆盖了多长？(重复覆盖的地区只计算一次)

### 解答 ###

用一个数组来标记区间段的覆盖情况，最后遍历这个标记数组就行了。

public class XianDuanLength {
        
    
        public static void main(String[] args) {
            SegMent segMent1 = new SegMent(2, 5);
            SegMent segMent2 = new SegMent(7, 10);
            SegMent segMent3 = new SegMent(16, 20);
            SegMent segMent4 = new SegMent(9, 12);
            SegMent[] segMents = { segMent1, segMent2, segMent3, segMent4 };
            System.out.println(getTotalLength(segMents));
        }
    
        public static int getTotalLength(SegMent[] segMents) {
            //找到最小起始点和最大终止点
            boolean flag[] = new boolean[100];
    
            int min = segMents[0].getStart();
            int max = segMents[0].getEnd();
            for (SegMent segMent : segMents) {
    
                //标记区间段
                for (int start = segMent.getStart(); start < segMent.getEnd(); start++) {
                    flag[start] = true;
                }
    
                if (segMent.getStart() < min) {
                    min = segMent.getStart();
                }
                if (segMent.getEnd() > max) {
                    max = segMent.getEnd();
                }
            }
            int length = 0;
            for (int i = min; i <= max; i++) {
    
                if (flag[i]) {
                    while (flag[i]) {
                        length++;
                        i++;
                    }
                }
            }
    
            return length;
        }
    
        /**
         * 判断点是否在区间内
         * @param point
         * @param segMent
         * @return
         */
        public static boolean isInSegMent(int point, SegMent segMent) {
            return segMent.getStart() <= point && point <= segMent.getEnd() ? true : false;
        }
    
        /**
         * 区间类
         */
        static class SegMent {
            private int start;
            private int end;
    
            public SegMent(int start, int end) {
                this.start = start;
                this.end = end;
            }
    
            public int getStart() {
                return start;
            }
    
            public void setStart(int start) {
                this.start = start;
            }
    
            public int getEnd() {
                return end;
            }
    
            public void setEnd(int end) {
                this.end = end;
            }
        }
    }