Сортировка алгоритма для основанной на несравнении проблемы вида?

Другими словами, Вы хотите оптимизировать полное время выполнения при формулировке двух ограничений (сильный: самая ранняя точка выполнения, слабого: приоритет)? Это называют ограничительная проблема удовлетворенности . Существуют специальные решатели для этого вида проблемы.

Кстати, решение jakber не работает. Даже без продолжительности, следующий пример, очевидно, перестал работать:

event a (priority = 1, start = 5)
event b (priority = 2, start = 0)

отсортированная последовательность была бы a, b, в то время как требуемый результат, конечно b, a.

Я думаю:

1. задачи Вида приоритетом
2. Вмещают задачи во временную шкалу, беря первый доступный слот после их earliestTime, который имеет дыру, достаточно большую для задачи.

Преобразовывают временную шкалу в список задачи, и ожидает (разрывов).

Вопросы:

1. позволенные разрывы?
2. задачи могут быть разделены?
3. , Учитывая задачи как в вопросе: лучше задержать b, чтобы завершить c или сделать d так, чтобы b мог запуститься вовремя?

Редактирование:

OS ответы на мои вопросы:

1. No (выход - если нет ничего для выполнения, я предполагаю, что у нас мог бы быть разрыв)
2. Никакой
3. Все еще не ясный, но я предполагаю, что пример предлагает выполненный c и задержку b.

В этом случае алгоритм мог бы быть:

1. Вид приоритетом
2. Сохраняет счетчик в течение текущего 'времени', запускающегося с Поиска t=0
3. , хотя отсортированный список, для самого высокого приоритетного объекта, который может быть запущен в t.
4. Добавляют объект к рабочему порядку и добавляют его продолжительность к t.
5. Повторение 3& 4, пока список не исчерпывается. Если нет никаких задач, выполнимых в t, и существуют задачи остающееся ожидание, засовывают 1 вторую задачу сна в рабочий порядок.

Этот алгоритм также O (n^2).

Походит на проблему, которую я имел на днях, которому ответили здесь .
Принятие Вы используете C#...

Я думаю, что необходимо отсортировать список дважды: сначала приоритетом и затем к самому раннему времени, с помощью любого стабильный алгоритм сортировки, например, вид вставки. Тем путем время будет увеличиваться, и в течение каждого раза вещи будут отсортированы по приоритету.

, Если Вы не видите что-то, которое я не, можно полностью проигнорировать продолжительность каждого события в целях вида.

http://en.wikipedia.org/wiki/Category:Stable_sorts

Если у Вас есть ограниченный набор приоритетных уровней, Вы могли бы сохранить ряд отсортированных по времени списков, 1 для каждого уровня. Каждый раз, когда Вам нужно следующее событие, проверьте заголовок каждого списка в первоочередном заказе, пока Вы не находите тот, время начала которого передало. (Отслеживайте минимальное время начала, в то время как Вы проверяете - в случае, если никакое событие еще не готово, Вы знаете который ожидать)

Кстати, в наиболее общем случае не может быть никакого решения (если разрывы не позволяются, как Douglas указал). Например:

Event a = new Event { priority = 1, duration = 1.0, earliestTime = 4.0 };
Event b = new Event { priority = 2, duration = 1.0, earliestTime = 4.0 };
Event c = new Event { priority = 3, duration = 1.0, earliestTime = 4.0 };
Event d = new Event { priority = 4, duration = 1.0, earliestTime = 4.0 };

Я не совсем уверен, что понимаю запутанность Вашей проблемы, но мой инстинкт говорит мне, что необходимо определить отношения между приоритетом и время начала. Пример был бы:

Event a = new Event { priority = 1, duration = 4.0, earliestTime = 1.0 };
Event b = new Event { priority = 2, duration = 5.0, earliestTime = 0.0 };

Так, мы идем вперед и запускаемся b во время = 0, или мы ожидаем галочки и затем запускаемся a, потому что это - более высокий приоритет? Предположим, что было больше событий с большим количеством приоритетов и более длительных компромиссов времени. Я думаю, что Вам нужно правило вроде, "если следующее событие является X более высокими приоритетами, и разрыв (между теперь и самое раннее время) является меньше, чем секунды Y, ожидайте и затем запустите более высокое приоритетное событие. иначе запустите низкоприоритетное событие (таким образом пододвигающий высокий приоритет обратно один)".

Вот некоторый код Python вроде ответа Douglas. Сначала мы сортируем по приоритету, затем мы приспосабливаем временную шкалу способом вида выбора:

#!/usr/bin/env python
MIN_PRIORITY = 100

class Event(object):
    def __init__(self, name, priority, duration, earliestTime):
        self.name = name
        self.priority = priority
        self.duration = duration
        self.earliestTime = earliestTime
    def __str__(self):
        return "%-10s:  P %3d  D %3.1f  T %3.1f" % (self.name, self.priority, self.duration, self.earliestTime)

def sortEvents(_events):
    def comparePriority(event1, event2):
        if event1.priority < event2.priority: return -1
        if event1.priority > event2.priority: return 1
        return 0

    # Get a copy of the events and sort by priority
    events = [e for e in _events]
    events.sort(cmp=comparePriority)

    # Select one event at a time, checking for compatibility with elapsed time
    elapsedTime = 0.0
    sortedEvents = []
    while events:
        minGap = events[0].earliestTime - elapsedTime
        for e in events:
            currentGap = e.earliestTime - elapsedTime
            if currentGap < minGap:
                minGap = currentGap
            if currentGap <= 0.0:
                sortedEvents.append(e)
                elapsedTime += e.duration
                events.remove(e)
                break

        # If none of the events fits, add a suitable gap
        if minGap > 0:
            sortedEvents.append( Event("gap", MIN_PRIORITY, minGap, elapsedTime) )
            elapsedTime += minGap
    return sortedEvents

if __name__ == "__main__":
    #e1 = Event("event1", 1, 1.0, 4.0)
    #e2 = Event("event2", 2, 1.0, 6.0)
    #e3 = Event("event3", 3, 1.0, 8.0)
    #e4 = Event("event4", 4, 1.0, 10.0)

    e1 = Event("event1", 1, 4.0, 0.0)
    e2 = Event("event2", 2, 5.0, 6.0)
    e3 = Event("event3", 3, 3.0, 0.0)
    e4 = Event("event4", 4, 2.0, 0.0)

    events = [e1, e2, e3, e4]

    print "Before:"
    for event in events: print event
    sortedEvents = sortEvents(events)
    print "\nAfter:"
    for event in sortedEvents: print event

Это кажется, что Вы действительно на самом деле делаете, хотят основанный на сравнении вид. Ваш ключ сортировки {earliestTime, приоритет}, в том порядке. Так как Вашим примером является pseudo-C#, я дам Вам pseudo-C# решение:

class Event : IComparable<Event>, IComparable{
    int    priority;
    double duration;
    double earliestTime;

    public int CompareTo(Event other){
        if(other == null)
            return 1; /* define: non-null > null */

        int cmp = earliestTime.CompareTo(other.earliestTime);
        if(cmp != 0)
            return cmp;

        /* earliestTimes were equal, so move on to next comparison */
        return priority.CompareTo(other.priority);
    }

   int IComparable.CompareTo(object other){ /* for compatibility with non-generic collections */
       if(other == null)
            return 1; /* define: non-null > null */

       Event e_other = other as Event;
       if(e_other == null) /* must have been some other type */
           throw new ArgumentException("Must be an Event", "other");

       return CompareTo(e_other); /* forward to strongly-typed implementation */
   }
}

Теперь Ваш список отсортирует, как Ваш утверждает, ожидают.

РЕДАКТИРОВАНИЕ :

Мое начальное предположение было то, что события будут выбраны от списка и переданы к отдельному потоку, так, чтобы диспетчер очереди мог исчерпать следующее событие вовремя, но из комментариев я получил, я получил идею, что, возможно, подход, который был однопоточным, и все же позволил событиям более высокого приоритета исчерпывать максимально близко, к их времени начала было более желательным. В этом случае эти CompareTo функция должна измениться следующим образом:

public int CompareTo(Event other){
    if(other == null)
        return 1; /* define: non-null > null */

    int cmp = priority.CompareTo(other.priority);

    if(cmp == 0)
        /*
         * calculate and compare the time each event will be late
         * if the other one were to start first.  This time may be
         * negative if starting one will not make the other one late
         */
        return (earliestTime + duration - other.earliestTime).CompareTo(
            other.earliestTime + other.duration - earliestTime);

    /*
     * they're different priorities. if the lower-priority event
     * (presume that greater priority index means lower priority,
     * e.g. priority 4 is "lower" priority than priority 1), would
     * would make the higher-priority event late, then order the
     * higher-priority one first.  Otherwise, just order them by
     * earliestTime.
     */
    if(cmp < 0){/* this one is higher priority */
        if(earliestTime <= other.earliestTime)
            /* this one must start first */
            return -1;

        if(other.earliestTime + other.duration <= earliestTime)
            /* the lower-priority event would not make this one late */
            return 1;

        return -1;
    }

    /* this one is lower priority */
    if(other.earliestTime <= earliestTime)
        /* the other one must start first */
        return 1;

    if(earliestTime + duration <= other.earliestTime)
        /* this event will not make the higher-priority one late */
        return -1;

    return 1;
}

Тест это против любых предположений, но я думаю, что это - то, что мы ищем.