编辑代码

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


public 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();
            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 + ")");
        }

    }

    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;
    }
}