(Dynamic programming) How to maximize room utilization with a list of meeting?

Question

I am trying this problem using dynamic programming

Problem:

Given a meeting room and a list of intervals (represent the meeting), for e.g.:

• interval 1: 1.00-2.00
• interval 2: 2.00-4.00
• interval 3: 14.00-16.00 ... etc.

Question:

How to schedule the meeting to maximize the room utilization, and NO meeting should overlap with each other?

Attempted solution

Below is my initial attempt in C# (knowing it is a modified Knapsack problem with constraints). However I had difficulty in getting the result correctly.

bool ContainsOverlapped(List<Interval> 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 bool Optimize(List<Interval> intervals, int limit, List<Interval> itemSoFar){
        if (intervals == null || intervals.Count == 0)
            return true; //no more choice

        if (Sum(itemSoFar) > limit) //over limit
            return false;

        var arrInterval = intervals.ToArray();

        //try all choices
        for (int i = 0; i < arrInterval.Length; i++){
            List<Interval> remaining = new List<Interval>();
            for (int j = i + 1; j < arrInterval.Length; j++) { 
                remaining.Add(arrInterval[j]);
            }

            var partialChoice = new List<Interval>();
            partialChoice.AddRange(itemSoFar);
            partialChoice.Add(arrInterval[i]);

            //should not schedule overlap
            if (ContainsOverlapped(partialChoice))
                partialChoice.Remove(arrInterval[i]);

            if (Optimize(remaining, limit, partialChoice))
                return true;
            else
                partialChoice.Remove(arrInterval[i]); //undo
        }

        //try all solution
        return false;
    }


public class Interval
{
    public bool IsOverlap(Interval other)
    {
        return (other.Start < this.Start && this.Start < other.End) || //other < this
                (this.Start < other.Start && other.End < this.End) || // this covers other
                (other.Start < this.Start && this.End < other.End) || // other covers this
                (this.Start < other.Start && other.Start < this.End); //this < other
    }
    public override bool Equals(object obj){
        var i = (Interval)obj;
        return base.Equals(obj) && i.Start == this.Start && i.End == this.End;
    }
    public int Start { get; set; }
    public int End { get; set; }
    public Interval(int start, int end){
        Start = start;
        End = end;
    }
    public int Duration{
        get{
            return End - Start;
        }
    }
}

Edit 1

Room utilization = amount of time the room is occupied. Sorry for confusion.

Edit 2

for simplicity: the duration of each interval is integer, and the start/end time start at whole hour (1,2,3..24)

Answer 1

I'm not sure how you are relating this to a knapsack problem. To me it seems more of a vertex cover problem.

First sort the intervals as per their start times and form a graph representation in the form of adjacency matrix or list.

The vertices shall be the interval numbers. There shall be an edge between two vertices if the corresponding intervals overlap with each other. Also, each vertex shall be associated with a value equal to the interval's duration.

The problem then becomes choosing the independent vertices in such a way that the total value is maximum.

This can be done through dynamic programming. The recurrence relation for each vertex shall be as follows:

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]

Note:
The vertices should be numbered in increasing order of their start times. Then if there are three vertices:
i < j < k, and if there is no edge between vertex i and vertex j, then there cannot be any edge between vertex i and vertex k.

Answer 2

Good approach is to create class that can easily handle for you.

First I create helper class for easily storing intervals

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;
    }
}

And then here is class Room, where all intervals are and which has method "addInterval", which returns true, if interval is ok and was added and false, if it does not.

btw : I got a checking condition for overlapping here : Algorithm to detect overlapping periods

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;
    }
}

Answer 3

While the more general problem (if you have multiple number of meeting rooms) is indeed NP-Hard, and is known as the interval scheduling problem.

Optimal solution for 1-d problem with one classroom:
For the 1-d problem, choosing the (still valid) earliest deadline first solves the problem optimally.

Proof: by induction, the base clause is the void clause - the algorithm optimally solves a problem with zero meetings.

The induction hypothesis is the algorithm solves the problem optimally for any number of k tasks.

The step: Given a problem with n meetings, hose the earliest deadline, and remove all invalid meetings after choosing it. Let the chosen earliest deadline task be T.
You will get a new problem of smaller size, and by invoking the algorithm on the reminder, you will get the optimal solution for them (induction hypothesis).
Now, note that given that optimal solution, you can add at most one of the discarded tasks, since you can either add T, or another discarded task - but all of them overlaps T - otherwise they wouldn't have been discarded), thus, you can add at most one from all discarded tasks, same as the suggested algorithm.

Conclusion: For 1 meeting room, this algorithm is optimal.

QED

high level pseudo code of the solution:

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

---

Clarification: This answer assumes "Room Utilization" means maximize number of meetings placed in the room.

Answer 4

Thanks all, here is my solution based on this Princeton note on dynamic programming.

Algorithm:

1. Sort all events by end time.
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]);
       }               
   }
   

The complete source-code:

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