200高分求高效时间排序算法和程序！
有个类里有1个开始时间start，一个结束时间end。

Java code

    class Data {
        public Date start;
        public Date end;
    }

希望写的方法定义如下。

Java code

    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种都可以。

另外，程序有一定性能要求。
希望即给出想法，也给出程序。 先谢谢大家。

------解决方案--------------------
看懂了，但是我能想到的办法宝宝你肯定也想到了，还是让大神来给个高效方案吧~
帮顶
------解决方案--------------------
排序用Comparator.compare(T o1,T o2) 方法就可以了。
不知道楼主说的分组是什么意思，分成几组？什么规则
------解决方案--------------------
我的想法：
比较方法：输入:时间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操作。
------解决方案--------------------
帮顶上去，再慢慢想想。
------解决方案--------------------
先简化出一个数据结构出来吧，将这一段段区间看成一个整体，按左端大小顺序依次设为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，所以还须采取适当的剪枝判断，这里还要研究一下如果顺势按直接继任组合的话，是不是就能得到最少组合，直觉上是每组中元素越多，组合数就应该越少。