(动态编程)如何通过会议列表最大限度地提高房间利用率

我不知道你是如何将其与背包问题联系起来的。对我来说，这似乎更像是一个顶点覆盖问题。

首先根据区间的起始时间对区间进行排序，并以邻接矩阵或列表的形式形成图形表示。

顶点应为区间数。如果相应的间隔彼此重叠，则两个顶点之间应存在边。此外，每个顶点应与一个等于间隔持续时间的值相关联。

然后，问题变成了以这样一种方式选择独立的顶点，即总值最大。

这可以通过动态编程来实现。每个顶点的递推关系如下：

V[i] = max{ V[j]            | j < i and i->j is an edge, 
            V[k] + value[i] | k < i and there is no edge between i and k }
Base Case V[1] = value[1]

注意：
顶点的编号应按其开始时间的升序排列。如果有三个顶点：
i<j<k、 如果在顶点i和顶点j之间没有边，则在顶点i与顶点k之间不可能有任何边。

好的方法是创建一个可以轻松处理的类。

首先，我创建了一个助手类，用于轻松存储间隔

public class FromToDateTime
{
    private DateTime _start;
    public DateTime Start
    {
        get
        {
            return _start;
        }
        set
        {
            _start = value;
        }
    }
    private DateTime _end;
    public DateTime End
    {
        get
        {
            return _end;
        }
        set
        {
            _end = value;
        }
    }
    public FromToDateTime(DateTime start, DateTime end)
    {
        Start = start;
        End = end;
    }
}

然后是类Room，所有的间隔都在其中，它有方法"addInterval"，如果interval是可以的并且被添加了，则返回true，如果不是，则返回false。

顺便说一句：我在这里得到了一个重叠的检查条件：检测重叠周期的算法

public class Room
{
    private List<FromToDateTime> _intervals;
    public List<FromToDateTime> Intervals
    {
        get
        {
            return _intervals;
        }
        set
        {
            _intervals = value;
        }
    }
    public Room()
    {
        Intervals = new List<FromToDateTime>();
    }
    public bool addInterval(FromToDateTime newInterval)
    {
        foreach (FromToDateTime interval in Intervals)
        {
            if (newInterval.Start < interval.End && interval.Start < newInterval.End)
            {
                return false;
            }
        }
        Intervals.Add(newInterval);
        return true;
    }
}

而更普遍的问题（如果你有多个会议室）确实是NP难问题，被称为间隔调度问题。

一个教室的一维问题的最优解决方案：
对于一维问题，选择（仍然有效的）最早截止日期首先以最优方式解决问题。

证明：通过归纳，基子句是void子句-该算法最优地解决了零会议的问题。

归纳假设是算法对于任意数量的k任务最优地解决问题。

步骤：给定n会议的问题，选择最早的截止日期，并在选择后删除所有无效的会议。让选择的最早截止日期任务为T。
你会得到一个更小的新问题，通过调用提醒上的算法，你会得到它们的最优解（归纳假设）。
现在，请注意，在给定最佳解决方案的情况下，您最多可以添加一个已丢弃的任务，因为您可以添加T，也可以添加另一个已放弃的任务-但所有这些任务都与T重叠-否则它们就不会被丢弃），因此，您可以从所有已丢弃任务中最多添加一个，与建议的算法相同。

结论：对于1个会议室，该算法是最优的。

QED

解决方案的高级伪代码：

findOptimal(list<tasks>):
   res = [] //empty list
   sort(list) //according to deadline/meeting end
   while (list.IsEmpty() == false):
        res = res.append(list.first())
        end = list.first().endTime()
        //remove all overlaps with the chosen meeting
        while (list.first().startTine() < end):
              list.removeFirst()
   return res

澄清：此答案假定"；房间利用率"；意味着最大限度地增加会议室中的会议次数。

谢谢大家，这是我基于普林斯顿关于动态编程的说明的解决方案。

算法：

1. 按结束时间对所有事件进行排序
2. 对于每个事件，查找p[n]-不与其重叠的最新事件（截止时间）

3. 计算优化值：在包括/不包括事件之间选择最佳值。

   Optimize(n) {
       opt(0) = 0;
       for j = 1 to n-th {
           opt(j) = max(length(j) + opt[p(j)], opt[j-1]);
       }               
   }
   

完整的源代码：

    namespace CommonProblems.Algorithm.DynamicProgramming {
    public class Scheduler {
        #region init & test
        public List<Event> _events { get; set; }
        public List<Event> Init() {
            if (_events == null) {
                _events = new List<Event>();
                _events.Add(new Event(8, 11));
                _events.Add(new Event(6, 10));
                _events.Add(new Event(5, 9));
                _events.Add(new Event(3, 8));
                _events.Add(new Event(4, 7));
                _events.Add(new Event(0, 6));
                _events.Add(new Event(3, 5));
                _events.Add(new Event(1, 4));
            }
            return _events;
        }
        public void DemoOptimize() {
            this.Init();
            this.DynamicOptimize(this._events);
        }
        #endregion
        #region Dynamic Programming
        public void DynamicOptimize(List<Event> events) {
            events.Add(new Event(0, 0));
            events = events.SortByEndTime();
            int[] eventIndexes = getCompatibleEvent(events);
            int[] utilization = getBestUtilization(events, eventIndexes);
            List<Event> schedule = getOptimizeSchedule(events, events.Count - 1, utilization, eventIndexes);
            foreach (var e in schedule) {
                Console.WriteLine("Event: [{0}- {1}]", e.Start, e.End);
            }
        }
        /*
        Algo to get optimization value:
        1) Sort all events by end time, give each of the an index.
        2) For each event, find p[n] - the latest event (by end time) which does not overlap with it.
        3) Compute the optimization values: choose the best between including/not including the event.
        Optimize(n) {
            opt(0) = 0;
            for j = 1 to n-th {
                opt(j) = max(length(j) + opt[p(j)], opt[j-1]);
            }
            display opt();
        }
        */
        int[] getBestUtilization(List<Event> sortedEvents, int[] compatibleEvents) {
            int[] optimal = new int[sortedEvents.Count];
            int n = optimal.Length;
            optimal[0] = 0;
            for (int j = 1; j < n; j++) {
                var thisEvent = sortedEvents[j];
                //pick between 2 choices:
                optimal[j] = Math.Max(thisEvent.Duration + optimal[compatibleEvents[j]],  //Include this event
                                       optimal[j - 1]);                                   //Not include
            }
            return optimal;
        }
        /* 
        Show the optimized events: 
            sortedEvents: events sorted by end time.
            index: event index to start with.
            optimal: optimal[n] = the optimized schedule at n-th event.
            compatibleEvents: compatibleEvents[n] = the latest event before n-th
         */
        List<Event> getOptimizeSchedule(List<Event> sortedEvents, int index, int[] optimal, int[] compatibleEvents) {
            List<Event> output = new List<Event>();
            if (index == 0) {
                //base case: no more event
                return output;
            }
            //it's better to choose this event
            else if (sortedEvents[index].Duration + optimal[compatibleEvents[index]] >= optimal[index]) {
                output.Add(sortedEvents[index]);
                //recursive go back
                output.AddRange(getOptimizeSchedule(sortedEvents, compatibleEvents[index], optimal, compatibleEvents));
                return output;
            }
            //it's better NOT choose this event
            else {
                output.AddRange(getOptimizeSchedule(sortedEvents, index - 1, optimal, compatibleEvents));
                return output;
            }
        }
        //compatibleEvents[n] = the latest event which do not overlap with n-th.
        int[] getCompatibleEvent(List<Event> sortedEvents) {
            int[] compatibleEvents = new int[sortedEvents.Count];
            for (int i = 0; i < sortedEvents.Count; i++) {
                for (int j = 0; j <= i; j++) {
                    if (!sortedEvents[j].IsOverlap(sortedEvents[i])) {
                        compatibleEvents[i] = j;
                    }
                }
            }
            return compatibleEvents;
        }
        #endregion
    }
    public class Event {
        public int EventId { get; set; }
        public bool IsOverlap(Event other) {
            return !(this.End <= other.Start ||
                    this.Start >= other.End);
        }
        public override bool Equals(object obj) {
            var i = (Event)obj;
            return base.Equals(obj) && i.Start == this.Start && i.End == this.End;
        }
        public int Start { get; set; }
        public int End { get; set; }
        public Event(int start, int end) {
            Start = start;
            End = end;
        }
        public int Duration {
            get {
                return End - Start;
            }
        }
    }
    public static class ListExtension {
        public static bool ContainsOverlapped(this List<Event> list) {
            var sortedList = list.OrderBy(x => x.Start).ToList();
            for (int i = 0; i < sortedList.Count; i++) {
                for (int j = i + 1; j < sortedList.Count; j++) {
                    if (sortedList[i].IsOverlap(sortedList[j]))
                        return true;
                }
            }
            return false;
        }
        public static List<Event> SortByEndTime(this List<Event> events) {
            if (events == null) return new List<Event>();
            return events.OrderBy(x => x.End).ToList();
        }
    }
}