活动时间问题描述：

有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();

        }

    }

}

作者：Czhenya

链接：https://czhenya.blog.csdn.net/article/details/78976022

来源：CSDN
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。