动态规划 -- 活动时间问题

活动时间问题描述：

有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行（最大兼容活动子集）。

动态规划法代码实现：

using System;

namespace _4_3_1动态规划_活动选择问题_自底向上
{
    class Program
    {
        static void Main(string[] args)
        {
            //活动开始时间s，结束时间f
            int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 24 };
            int[] f = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24 };

            //13是活动个数
            List<int>[,] resultList = new List<int>[13, 13];
            //初始值设空的集合
            for (int a = 0; a < 13; a++)
            {
                for (int b = 0; b < 13; b++)
                {
                    resultList[a, b] = new List<int>();
                }
            }



            for (int j = 0; j < 13; j++)      //j=2 时内层循环才会执行
            {
                for (int i = 0; i < j - 1; i++)
                {
                    //S(ij) i结束之后j开始之前的活动集合
                    //f[i] s[j] 这个时间区间内的所有活动
                    List<int> sij = new List<int>();
                    for (int k = 1; k < s.Length-1; k++)
                    {
                        if (s[k] >= f[i] && f[k] <= s[j])
                        {
                            sij.Add(k);
                        }
                    }
                    if (sij.Count > 0)
                    {
                        //result[i,j] = max{result[i,k]+result[k,j]+1}
                        int maxCount = 0;
                        //用于保存ij之间的最大活动时间
                        List<int> tempList = new List<int>();
                        foreach (int k in sij)
                        {
                            int count = resultList[i, k].Count + resultList[k, j].Count + 1;
                            if (maxCount < count)
                            {
                                maxCount = count;
                                //Union()用于合并量List
                                tempList = resultList[i, k].Union<int>(resultList[k, j]).ToList();
                                tempList.Add(k);
                            }
                        }
                        resultList[i, j] = tempList;
                    }                   
                }
            }
            List<int> temp = resultList[0, 12];
            foreach (int item in resultList[0, 12])
            {
                Console.WriteLine(item);
            }
            //此代码运行结果是1 4 8 11
            Console.ReadKey();
        }
    }
}