编辑代码

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;

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) {
                
                 if (left.end < right.end){
                     return -1;
                 }
                 else if (left.end == right.end) {
                     return 0;
                 }
                 else {
                     return 1;
                 }
             }
         }); 

        //找出不相交的区间
        uncrosssedSections.add(sections[0]);
        for (int i = 1; i < sections.length; i++) {
            SectionItem last = uncrosssedSections.getLast();
            //如果当前区间的开始位置大于等于前一个不相交区间的结束位置，
            //则将当前区间加入到uncrossedSections链表中。
            if (last.end <= sections[i].start) { 
                uncrosssedSections.add(sections[i]);
            }
        }

        return uncrosssedSections;
    }

    public static void test() {
        SectionItem[] sections = {
            new SectionItem(6, 8),
            new SectionItem(2, 4),
            new SectionItem(3, 5),
            new SectionItem(1, 5),
            new SectionItem(5, 9),
            new SectionItem(8, 10),
            new SectionItem(5,7),
            new SectionItem(7,9),
            new SectionItem(9,10)
        };

        LinkedList<SectionItem> uncrossedSections = findUncrossedSections(sections);

        System.out.println("找到如下不相交的区间：");
        for (int i = 0; i < uncrossedSections.size(); ++i) {
            System.out.println("(" + uncrossedSections.get(i).start + "," + uncrossedSections.get(i).end + ")");
        }
	}
}