编辑代码

package greedy;

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

public class Section {
    public static LinkedList<SectionItem> findUncrossedSections(SectionItem[] sections) {
        LinkedList<SectionItem> uncrossedSections = 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;
                }
            }
        });

        // 找出不相交的区间
        int lastEnd = sections[0].end;
        for (int i = 1; i < sections.length; i++) {
            if (sections[i].start > lastEnd) {
                uncrossedSections.add(new SectionItem(lastEnd, sections[i].end));
                lastEnd = sections[i].end;
            }
        }

        return uncrossedSections;
    }

    public static void main(String[] args) {
        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) };

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

    }

}

class SectionItem {
    public int start;
    public int end;

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