Алгоритм сортировки для задачи сортировки, не основанной на сравнении?

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

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

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

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

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

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

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

На самом деле это больше, чем проблема сортировки. Это проблема планирования одной машины с датами выпуска. В зависимости от того, что вы пытаетесь сделать, проблема может быть NP-Hard. Например, если вы пытаетесь имитировать взвешенную сумму времени завершения (вес обратно пропорционален приоритету), проблема будет в категоризированы как

1|ri;pmtn|Σ wiCi 

и является NP-трудным. По этой теме существует множество документы, но это может быть больше, чем вам нужно.

В вашем случае вам никогда не нужно решение с пробелами, поэтому вам может просто понадобиться простая симуляция дискретного события (O (n log (n))) времени. Вам нужно сохранить Release_jobs как приоритетную очередь.

unreleased_jobs = jobs  // sorted list of jobs, by release date
released_jobs = {}      // priority queue of jobs, by priority
scheduled_jobs = {}     // simple list
while (!unreleased_jobs.empty() || !released_jobs.empty()) {

    while (unreleased_jobs.top().earliestTime  <= t) {
        released_jobs.push(unreleased_jobs.pop())
    }
    if (!released_jobs.empty()) {
       next_job = released_jobs.pop();
       scheduled_jobs.push_back(next_job)
       t = t + next_job.duration
    } else {
       // we have a gap
       t = unreleased_jobs.top().earliestTime
    }
}

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

Похоже, вам действительно нужна сортировка на основе сравнения. Ваш ключ сортировки - {earliestTime, priority} в указанном порядке. Поскольку ваш пример - псевдо-C#, я дам вам решение псевдо-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;
}

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

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

Я думаю:

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

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

Вопросов:

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

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

О, ответы на мои вопросы таковы:

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

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

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

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

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

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 в соответствии с ответом Дугласа. Сначала мы сортируем по приоритету, затем подбираем временную шкалу в режиме сортировки по выбору:

#!/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