编辑代码

import java.util.*;

class Main {
    public static void main(String[] args) {
        Section.test();
    }
}

class SectionItem {
    public int start;
    public int end;
    
    public SectionItem(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

class Section {
    
    public static LinkedList<SectionItem> findUncrossedSections(SectionItem[] sections) {
        LinkedList<SectionItem> uncrosssedSections = new LinkedList<SectionItem>(); // 记录找到的区间
        
        // 对区间按照终点从小到大排列
        Arrays.sort(sections, new Comparator<SectionItem>() {
            public int compare(SectionItem left, SectionItem right) {
                
                return Integer.compare(left.end, right.end);
            }
        });
        
        //找出不相交的区间
        uncrosssedSections.add(sections[0]);
        for (int i = 1; i < sections.length; i++) {
            SectionItem last = uncrosssedSections.getLast();
            if (last.end <= sections[i].start) {
                uncrosssedSections.add(sections[i]);
            }
        }
        
        return uncrosssedSections;
    }
    
    public static void test() {
        SectionItem[] sections = {
                new SectionItem(2, 5),
                new SectionItem(5, 7),
                new SectionItem(4, 5),
                new SectionItem(6, 9),
                new SectionItem(2, 6),
                new SectionItem(6, 9),
                new SectionItem(1, 9),
                new SectionItem(4, 10),
                new SectionItem(8, 10),
        };
        
        LinkedList<SectionItem> uncrossedSections = findUncrossedSections(sections);
        
        System.out.println("不相交的区间：");
        for (SectionItem uncrossedSection : uncrossedSections) {
            System.out.println("(" + uncrossedSection.start + "," + uncrossedSection.end + ")");
        }
    }
}