200高分求高效时间排序算法和程序！

Question

有个类里有1个开始时间start，一个结束时间end。 class Data {
public Date start;
public Date end;
}
希望写的方法定义如下。 public static List<Data>[] sortDate(List<Data> input) {

}input 为Data的List乱序。 输出是按以下要求排好序的。
1) 将Data分组，分组要求，每组里的Data的开始和结束时间没有重叠。（但边界时，结束时间可以是另一个的开始时间。即一天重叠可以。）
2）输出的分组最少。（数组长度尽量最小。）
3）每组都已排序。例如：（都好左边为开始日，右边为结束日。 假设数字都是2012年9月某日。即写9就是2012年9月9日）
2,8
5,9
12,18
1,5
9,13经人工考虑上面应该被分为2组。
答案A
1,5    5,9     12,18
2,8    9,13
答案B
1,5    5,9     9,13
2,8    12,18以上2中答案都可，输出任意1种都可以。另外，程序有一定性能要求。
希望即给出想法，也给出程序。 先谢谢大家。

Answer 1

排序用Comparator.compare(T o1,T o2) 方法就可以了。
不知道楼主说的分组是什么意思，分成几组？什么规则

Answer 2

我的想法：
比较方法：输入:时间A、B;输出状态：B<A、B<A并紧挨、AB重叠、B>A并紧挨、B>A;1、第一个元素和后边每元素比较，B<A放入集合a，A>B放入集合b，重叠放入集合c，紧挨则让AB俩“相加”，并重新比较a或b;
2、对啊集合a、b进行1操作（递归），最后结果相加，等到一个分组；
3、对集合c进行1、2操作。

Answer 3

先简化出一个数据结构出来吧，将这一段段区间看成一个整体，按左端大小顺序依次设为a,b,c...define a = [1, 5] 
define b = [2, 8]
define c = [5, 9] 
define d = [9, 13]
define e = [12, 18] 将其看做节点，再整理出各节点的直接后继，记作：
a(c)
b(d, e)
c(d, e)
d()
e()当然每一组中未必必须有直接后继节点，但这样的话再计算会方便很多，至少有一点可以肯定，
最终分组数 n>=Number(a, b)=2  因为两始节点有重叠，必互不相容于对方组。这里如果用穷举的话，两结果：
1.
(a c d)
(b e)2.
(a c e)
(b d)这里，如果a跳过c直接与c的后继组成一组的话，势必会多出一组，不是c就是b，所以还须采取适当的剪枝判断，这里还要研究一下如果顺势按直接继任组合的话，是不是就能得到最少组合，直觉上是每组中元素越多，组合数就应该越少。

Answer 4

常规做法
按开始(结束)时间大小顺序排序input
遍历input，取不重叠的时间段分组import java.util.*;
class Data {
    Date start;
    Date end;
    
    public String toString() {
        return String.format("[%te,%te]", start, end);
    }
}public class Test {
    public static void main(String[] args) throws Throwable {
        List<Data> input = new ArrayList<Data>();
        int[][] testData = {{2,8}, {5,9}, {12,18}, {1,5}, {9,13}};
        Calendar c = Calendar.getInstance();
        c.set(Calendar.MONTH, 8);
        for (int[] td : testData) { //测试数据
            Data d = new Data();
            c.set(Calendar.DATE, td[0]);
            d.start = c.getTime();
            c.set(Calendar.DATE, td[1]);
            d.end = c.getTime();
            input.add(d);
        }
        
        List<Data>[] arr = sortData(input);
        for (List<Data> list : arr) {
            for (Data d : list) {
                System.out.printf("%s ", d);
            }
            System.out.println();
        }
    }
    
    @SuppressWarnings("unchecked")
    public static List<Data>[] sortData(List<Data> input) {
        List<List<Data>> result = new ArrayList<List<Data>>();
        List<Data> org = new LinkedList<Data>(input);
        Collections.sort(org, new Comparator<Data>() { //排序
            public int compare(Data d1, Data d2) {
                if (d1.start.before(d2.start)) return -1;
                else if (d1.start.after(d2.start)) return 1;
                else {
                    return (d1.end.before(d2.end) ? -1 : (d1.end.after(d2.end) ? 1 : 0));
                }
            }
        });
        
        while (org.size() > 0) { //遍历分组，直到分组结束
            result.add(new ArrayList<Data>());
            List<Data> current = result.get(result.size()-1);
            current.add(org.remove(0));
            for (int i=0; i<org.size(); i++) {
                if (current.get(current.size()-1).end.after(org.get(i).start)) continue;
                current.add(org.remove(i--));
            }
        }
        
        return result.toArray(new List[0]);
    }
}

Answer 5

结贴结得好快啊，我觉得主要难度就是：不用穷举似乎不太容易的到最优解；用穷举又有点违反了性能要求。我有个不太成熟的想法，就是用“图”来做这个事情。以楼主数据举例：
A 2,8
B 5,9
C 12,18
D 1,5
E 9,13可以形成5个节点的有向图，每个节点之间存在距离（距离就是 开始减结束，负数说明不可到达）
举例来说：
A<-->B 之间，不可到达；双方的开始与结束相减都是负数。
A--->C 单向，A 到 C 的距离是：12 - 8 = 4。
A<-->D 之间，不可到达。
A--->E 之间，A 到 E 的距离是：1。
那么最后可以构成一个完整的“有向图”。楼主的问题转化为“有向图的最少N笔画问题”，这种问题记得是有比较好的算法进行求解的。以上是我不成熟的想法，供楼主参考。