Алгоритм быстрой сортировки целых чисел

Question

У меня есть несортированные пары целых чисел, которые представляют некоторые временные интервалы (первое число всегда меньше второго). Проблема состоит в том, чтобы назначить целое число, так называемый номер канала (0..x) для каждого временного интервала, так чтобы интервалы, которые не сталкиваются, разделяли один и тот же канал. Наименьшее количество каналов должно быть использовано.

Например, эти интервалы будут использовать 2 канала:

50 100 // 1

10 70 // 0

80 200 // 0

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

Да, это задание, которое я получил от Университета, и оно уже реализовано, но кто-нибудь может подсказать, как сделать код быстрее? Какой алгоритм использовать, чтобы сортировка, цепочка пар была максимально быстрой? Длина входного массива составляет до 10 миллионов элементов.

Вот код:

#include <cstdlib>
#include <cstdio>
#include <iostream>
using namespace std;   

struct TPhone
 {
   unsigned int    m_TimeFrom;
   unsigned int    m_TimeTo;
   unsigned int    m_Channel;
 };

 class TElement
 {
 public:

  TPhone m_data;
  int index;

  TElement(TPhone  * const data, int index_)
  {
    m_data.m_TimeFrom=data->m_TimeFrom;
    m_data.m_TimeTo=data->m_TimeTo;
    m_data.m_Channel=-1;
    index=index_;
  }
  TElement()
  {
  }
 };

int FindNext(TElement** sorted_general_array, int general_array_size, int index_from)
{
  for (int i=index_from+1; i<general_array_size; i++ )
  {
    if (sorted_general_array[i]->m_data.m_TimeFrom > sorted_general_array[index_from]->m_data.m_TimeTo)
    {
      if (sorted_general_array[i]->m_data.m_Channel==(unsigned int)-1)
      {
        return i;
      }
    }
  }
  return -1;
}

int AssignChannels(TElement **sorted_general_array, int general_array_size)
{
  int current_channel=-1;
  for (int i=0; i<general_array_size; i++)
    {
      if (sorted_general_array[i]->m_data.m_Channel==(unsigned int)-1)
      {
        current_channel++;
        sorted_general_array[i]->m_data.m_Channel=current_channel;
        //cout << sorted_general_array[i]->m_data.m_TimeFrom << " " << sorted_general_array[i]->m_data.m_TimeTo << " " << sorted_general_array[i]->m_data.m_Channel << endl;
        int next_greater=i;
        while (1)
        {
          next_greater=FindNext(sorted_general_array,general_array_size,next_greater);
          if (next_greater!=-1)
          {
            sorted_general_array[next_greater]->m_data.m_Channel=current_channel;
            //cout << sorted_general_array[next_greater]->m_data.m_TimeFrom << " " << sorted_general_array[next_greater]->m_data.m_TimeTo << " " << sorted_general_array[next_greater]->m_data.m_Channel << endl;
          }
          else
          {
            break;
          } 
        }
      }
    }
    return current_channel;
}

int AllocChannels ( TPhone  * const * req, int reqNr )
 {
  //initialize
  int count_array_size=1700000;
  int * count_array;
  count_array=new int [count_array_size];
  for (int i=0; i<count_array_size; i++)
  {
     count_array[i]=0;
  }
  //
  int general_array_size=reqNr;
  TElement ** general_array;
  general_array=new TElement *[general_array_size];
  for (int i=0; i<general_array_size; i++)
  {
    general_array[i]= new TElement(req[i],i);
  }
  //--------------------------------------------------
  //counting sort
  //count number of each element
  for (int i=0; i<general_array_size; i++)
  {
    count_array[general_array[i]->m_data.m_TimeFrom]++;
  }
  //modify array to find postiions
  for (int i=0; i<count_array_size-1; i++)
  {
    count_array[i+1]=count_array[i+1]+count_array[i];
  }
  //make output array, and fill in the sorted data
  TElement ** sorted_general_array;
  sorted_general_array=new TElement *[general_array_size];

  for (int i=0; i <general_array_size; i++)
  {
    int insert_position=count_array[general_array[i]->m_data.m_TimeFrom]-1;
    sorted_general_array[insert_position]=new TElement;

    //cout << "inserting " << general_array[i]->m_data.m_TimeFrom << " to " << insert_position << endl;
    sorted_general_array[insert_position]->m_data.m_TimeFrom=general_array[i]->m_data.m_TimeFrom;
    sorted_general_array[insert_position]->m_data.m_TimeTo=general_array[i]->m_data.m_TimeTo;
    sorted_general_array[insert_position]->m_data.m_Channel=general_array[i]->m_data.m_Channel;
    sorted_general_array[insert_position]->index=general_array[i]->index;


    count_array[general_array[i]->m_data.m_TimeFrom]--;
    delete  general_array[i];
  }
  //free memory which is no longer needed
  delete [] general_array;
  delete [] count_array;
  //--------------------------------------------------

  int channels_number=AssignChannels(sorted_general_array,general_array_size);
  if (channels_number==-1)
  {
    channels_number=0;
  }
  else
  {
    channels_number++;
  }

  //output
  for (int i=0; i<general_array_size; i++)
  {
    req[sorted_general_array[i]->index]->m_Channel=sorted_general_array[i]->m_data.m_Channel;
  }


  //free memory and return
  for (int i=0; i<general_array_size; i++)
  {
    delete sorted_general_array[i];
  }
  delete [] sorted_general_array;

  return channels_number;
 }                                                             


int main ( int argc, char * argv [] )
 {
   TPhone ** ptr;
   int cnt, chnl;

   if ( ! (cin >> cnt) ) return 1;

   ptr = new TPhone * [ cnt ];
   for ( int i = 0; i < cnt; i ++ )
    {
      TPhone * n = new TPhone;
      if ( ! (cin >> n -> m_TimeFrom >> n -> m_TimeTo) ) return 1;
      ptr[i] = n;
    }

   chnl = AllocChannels ( ptr, cnt );

   cout << chnl << endl;
   for ( int i = 0; i < cnt; i ++ )
    {
      cout << ptr[i] -> m_Channel << endl;
      delete ptr[i];
    }
   delete [] ptr; 
   return 0;
  }

Answer 1

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

1. Определите ваш интервальный класс следующим образом, добавив два определения встроенных функций (то, что я использую структуру для TimeDescriptor, это просто вопрос стиля, хотя этот код не очень стильный):

   typedef struct TimeDescriptor {
       unsigned time;
       bool isEnd;
   } TimeDescriptor;
   
   class TimeInterval {
       public:
           TimeDescriptor start, end;
           unsigned channel;
   
           TimeInterval(unsigned startTime, unsigned endTime) {
               start = (TimeDescriptor){ startTime, false };
               end = (TimeDescriptor){ endTime, true };
           }
   }
   
   inline TimeInterval* getInterval(TimeDescriptor* me) {
       return (me->isEnd) ? (TimeInterval*)(me - 1) : (TimeInterval*)me;
   }
   
   inline TimeDescriptor* getOther(TimeDescriptor* me) {
       return (me->isEnd) ? (me - 1) : (me + 1);
   }
   

2. Создайте массив указателей на все TimeDescriptors, по два для каждого TimeInterval (один для начала, другой для конца).

3. Отсортируйте этот массив указателей TimeDescriptor по времени. Убедитесь, что вы используете isEnd помечать как вторичный ключ сортировки. Я не уверен, как определяются конфликты интервалов, т. Е. Конфликтуют ли два интервала (20, 30) и (30, 40) или нет, если они конфликтуют, сортируют время окончания после времени начала с одинаковым значением, если они не конфликтовать, сортировать время окончания до времени начала с тем же значением.

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

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

   Самый простой способ реализовать такой стек - это, вероятно, запрограммировать небольшой класс, который использует std::vector<unsigned> хранить свободные каналы, и это отслеживает самый большой номер канала, когда-либо использовавшийся. Всякий раз, когда всплывающий запрос не может быть обслужен из внутреннего хранилища, новый номер канала создается путем увеличения наибольшего номера канала на единицу.

5. Пройдите через ваш отсортированный массив TimeDescriptors. Каждый раз, когда вы сталкиваетесь с временем начала, извлекайте номер канала и сохраняйте его в соответствующем TimeInterval (используя getInterval()). Каждый раз, когда вы сталкиваетесь с временем окончания, вставьте номер его канала обратно в массив свободных каналов.

6. Когда вы закончите, ваш свободный стек каналов покажет вам максимальное количество каналов, которые вы использовали одновременно, и каждый TimeInterval будет содержать правильный номер канала для использования. Вы даже можете эффективно вычислить все цепочки интервалов, которые совместно используют канал, просто прибегая к массиву TimeInterval по номеру канала...

Answer 2

На этот вопрос уже есть принятый ответ. Однако я хотел описать немного другой подход, чем принятый ответ.

Вы должны измерить

Вы не сможете ничего рассказать о производительности без измерения. И чтобы измерить нам нужны контрольные примеры. Поэтому мне кажется, что первая задача - создать программу, которая будет генерировать контрольные примеры.

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

#include <iostream>
#include <random>

int
main()
{
    const unsigned N = 10000000;
    std::mt19937_64 eng(0);
    std::uniform_int_distribution<unsigned> start_time(0, N);
    std::chi_squared_distribution<> duration(4);
    std::cout << N << '\n';
    for (unsigned i = 0; i < N;)
    {
        unsigned st = start_time(eng);
        unsigned et = st + static_cast<unsigned>(duration(eng));
        if (et > st)
        {
            std::cout << st << ' ' << et << '\n';
            ++i;
        }
    }
}

Можно варьировать значение Nдиапазон заполнения механизма случайных чисел (если не выбран механизм случайных чисел), диапазон времени запуска и тип / форма распределения вероятностей временных интервалов. Я вытащил каждый из этих вариантов из воздуха. Ваш профессор может иметь лучшие идеи по созданию разумных контрольных примеров для этой проблемы. Но измерять что-то лучше, чем ничего не измерять.

Использоватьstd::lib

Стандартная библиотека полна контейнеров и алгоритмов. Этот код не только отлажен, но и эффективен. Повторное использование этого кода является хорошим стилем кодирования, потому что:

1. Он учит вас распознавать контейнеры и когда использовать какой контейнер.
2. Он учит вас распознавать алгоритмы и когда использовать какой алгоритм.
3. Это может помочь вам определить необходимость и кодировать ваши собственные контейнеры и алгоритмы, когда они не предоставляются std:lib,
4. Это делает ваш код намного проще для чтения другими, потому что они будут знать о стандартных контейнерах и алгоритмах.
5. Это делает ваш код намного проще для отладки, потому что вероятность ошибок в вашем коде намного выше, чем вероятность ошибок в std::lib (хотя ни одна вероятность не равна нулю).

Например

Я увеличил ваш TPhone Структура с I/O, чтобы облегчить сложность I/O, которую вы делаете в main:

friend
std::istream&
operator>>(std::istream& is, TPhone& p)
{
    return is >> p.m_TimeFrom >> p.m_TimeTo;
}

friend
std::ostream&
operator<<(std::ostream& os, const TPhone& p)
{
    return os << '{' <<  p.m_TimeFrom << ", "
                     <<  p.m_TimeTo << ", "
                     << p.m_Channel << '}';
}

И я выбрал vector<TPhone> удерживать все звонки. Это упрощает это:

int main ( int argc, char * argv [] )
 {
   TPhone ** ptr;
   int cnt, chnl;

   if ( ! (cin >> cnt) ) return 1;

   ptr = new TPhone * [ cnt ];
   for ( int i = 0; i < cnt; i ++ )
    {
      TPhone * n = new TPhone;
      if ( ! (cin >> n -> m_TimeFrom >> n -> m_TimeTo) ) return 1;
      ptr[i] = n;
    }

Вплоть до этого:

int main()
{
    using namespace std;
    vector<TPhone> ptr;
    int cnt;
    if (!(cin >> cnt)) return 1;
    ptr.reserve(cnt);
    for (int i = 0; i < cnt; ++i)
    {
        TPhone n;
        if (!(cin >> n)) return 1;
        ptr.push_back(n);
    }

И, как оказалось, моя версия более эффективна, чем ваша. Я получаю эту эффективность "бесплатно", просто научившись использовать std::vector,

AllocChannels Теперь можно взять std::vector<TPhone>&:

int
AllocChannels(std::vector<TPhone>& ptr)

Здесь я использовал самый простой из возможных алгоритмов. Не потому, что я думал, что это может быть быстрее, а потому, что вам нужна базовая линия для сравнения. И, как оказалось, просто не всегда медленно...

int
AllocChannels(std::vector<TPhone>& ptr)
{
    using namespace std;
    if (ptr.size() == 0)
        return 0;
    // sort TPhone's by x.m_TimeFrom
    sort(ptr.begin(), ptr.end(), [](const TPhone& x, const TPhone& y)
                                       {
                                           return x.m_TimeFrom < y.m_TimeFrom;
                                       });
   // Create channel 0 and mark it as busy by the ptr[0] until ptr[0].m_TimeTo
    vector<unsigned> channels(1, ptr.front().m_TimeTo);
    ptr.front().m_Channel = 0;
   // For each call after the first one ...
    for (auto i = next(ptr.begin()); i != ptr.end(); ++i)
    {
        // Find the first channel that isn't busy at this m_TimeFrom
        auto j = find_if(channels.begin(), channels.end(),
                                           [&](unsigned tf)
                                             {
                                                 return tf < i->m_TimeFrom;
                                             });
        if (j != channels.end())
        {
           // Found a non-busy channel, record it in use for this call
           i->m_Channel = j - channels.begin();
           // Mark the channel busy until m_TimeTo
           *j = i->m_TimeTo;
        }
        else
        {
            // Record a new channel for this call
            i->m_Channel = channels.size();
            // Create a new channel and mark it busy until m_TimeTo
            channels.push_back(i->m_TimeTo);
        }
    }
    return channels.size();
}

Я использовал несколько функций C++11, потому что они удобны (например, auto и lambdas). Если у вас нет этих функций, их легко обойти в C++03. Основной алгоритм, который я использовал, это просто отсортировать по m_TimeFrom, а затем выполните линейный обход отсортированного списка вызовов, и для каждого вызова выполните линейный поиск по набору каналов в поисках канала, который не используется (создайте новый, если все используются). Обратите внимание на использование стандартных алгоритмов sort а также find_if, Нет смысла в их повторной реализации, особенно для базового теста.

я использовал <chrono> ко времени все

auto t0 = chrono::high_resolution_clock::now();
int chnl = AllocChannels(ptr);
auto t1 = std::chrono::high_resolution_clock::now();

Я проинструктировал ваш код точно таким же образом, чтобы я мог проверить оба. Вот мои результаты, сначала сгенерировав тестовый случай длины = {100, 1000, 10000, 100000, 1000000, 10000000}, и для каждой длины, выполняющей сначала ваш код, а затем мой, оба с использованием только этого вывода:

cout << "#intervals = " << cnt << '\n';
cout << "#channels = " << chnl << '\n';
cout << "time = " << chrono::duration<double>(t1-t0).count() << "s\n";

Вот что я получил:

$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out > test.dat
$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out < test.dat
#intervals = 100
#channels = 10
time = 0.00565518s
$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out < test.dat
#intervals = 100
#channels = 10
time = 6.934e-06s

$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out > test.dat
$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out < test.dat
#intervals = 1000
#channels = 17
time = 0.00578557s
$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out < test.dat
#intervals = 1000
#channels = 17
time = 5.4779e-05s

$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out > test.dat
$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out < test.dat
#intervals = 10000
#channels = 16
time = 0.00801314s
$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out < test.dat
#intervals = 10000
#channels = 16
time = 0.000656864s

$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out > test.dat
$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out < test.dat
#intervals = 100000
#channels = 18
time = 0.0418109s
$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out < test.dat
#intervals = 100000
#channels = 18
time = 0.00788054s

$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out > test.dat
$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out < test.dat
#intervals = 1000000
#channels = 19
time = 0.688571s
$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out < test.dat
#intervals = 1000000
#channels = 19
time = 0.093764s

$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out > test.dat
$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out < test.dat
Segmentation fault: 11
$ clang++ -stdlib=libc++ -std=c++11 test.cpp -O3
$ a.out < test.dat
#intervals = 10000000
#channels = 21
time = 1.07429s

Резюме

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

Я не знаю причину ошибки сегментации для вашего случая с N = 10000000. Я не потратил время на изучение вашего кода. Откровенно говоря, я считаю ваш код сложным.

Я забыл написать тест на правильность. Это должно было быть моим первым шагом. Вывод правильный? Я стал ленивым и просто взглянул на дело N == 100, чтобы увидеть, выглядит ли оно правильно.

Из-за повторного использования std:: Containers и алгоритмов мой код будет гораздо проще настроить для повышения производительности, чем ваш. Например, вы можете попробовать std::lower_bound (бинарный поиск) вместо std::find_ifи измерить, если это улучшает вещи или нет (я держу пари, но вы должны измерить, и с test.dat что ты уважаешь).

Разложите ваш код на контейнеры и алгоритмы. Повторно используйте std-определенные контейнеры и алгоритмы, когда они существуют, иначе создайте свои собственные, которые можно будет повторно использовать в вашем будущем кодировании. Будучи студентом, я ожидаю, что стандартные определения будут достаточны для большинства ваших случаев использования.

Всегда проверяйте на правильность (как я не смог сделать это здесь:-)). Не думайте о производительности без измерения. Бинарный поиск не всегда быстрее линейного поиска, хотя он имеет лучшую асимптотическую сложность. И входные данные могут сильно повлиять на производительность ваших алгоритмов. Узнайте, как генерировать различные входные данные, чтобы понять, как могут повлиять ваши алгоритмы. <random> отлично подходит для этой задачи.

Answer 3

Храните записи в std::vector<TPhone> вместо того, чтобы в TPhone **, Это будет макет подряд TPhone объекты последовательно в памяти, что приводит к уменьшению количества кешей.

Эксперимент с другими типами данных, чем unsigned int для членов TPhone, Увидеть <cstdint> для типов, которые вы можете попробовать.

Answer 4

Извините за то, что я здесь некромант, но, прочитав вопрос и разместив ответы, я просто не мог его отпустить.

Алгоритм назначения канала:

У проблемы есть жадное решение, которое чрезвычайно эффективно. Рассмотрим следующую рекурсию:

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

Это даст оптимальное количество каналов. Доказательство тривиально, по индукции по числу интервалов.

Сортировка входов

Ключ к скорости лежит в том, "если не существует никаких конфликтов". Это означает, что будут проводиться сравнения между тем, что было обработано, и тем, что осталось обработать, и должно быть достаточно легко убедить себя, что сортировка входных данных вначале будет быстрее, чем сортировка их по мере их обработки (или нет). сортировка их вообще).

Если вы не уверены, рассмотрите следующие две крайности:

1. Все интервалы перекрываются.
2. Нет интервалов перекрытия.

Выбор алгоритма сортировки

Нам нужно отсортировать входные данные по времени начала, а затем по времени. Это достаточно просто, если мы выбираем стабильную сортировку и сортируем сначала по времени окончания, а затем по времени начала. Стабильная версия Counting Sort, вероятно, является лучшим вариантом, учитывая, что все значения являются целыми числами; количество входов намного больше, чем диапазон входов; и использование памяти не является важным фактором. Этот тип является линейным по количеству входов в этих условиях.

Сортировка каналов

При сортировке входных данных нам нужно только сравнить каждый интервал с последним интервалом, назначенным каждому каналу. В крайнем случае, когда интервалы не перекрываются, этот алгоритм является линейным: O(n) sort, + O(n) processing = O(n). С другой стороны крайности, где все интервалы перекрываются, без дальнейших улучшений алгоритм будет квадратичным.

Чтобы улучшить это, а не сравнивать по всем каналам, если каналы были отсортированы по самому раннему времени окончания, то конфликт с первым каналом автоматически указывает на конфликт всех каналов. Тогда для каждого интервала нам нужно только 1 сравнение, и все, что требуется для поддержания отсортированного порядка каналов.

Для этого я бы предложил хранить каналы в минимальной куче (к концу времени). Канал, необходимый для сравнения, всегда будет наверху. Загляните на этот канал и:

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

В наихудшем сценарии кошмара отсортированные интервалы будут иметь монотонно увеличивающееся время начала и монотонно уменьшающееся время окончания. Это дает нам наихудший случай для алгоритма O(n + lg 1 + lg 2 + ... + lg n) = O(n + lg(n!)) = O(n + n lg n) = O(н лг н)

Реальный мир

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

Answer 5

Если у вас есть отсортированная коллекция, зачем вам использовать линейный поиск? Используйте бинарный поиск.

Answer 6

Пусть [a_i, b_i) будут вашими интервалами, i = 1, ..., n. Вы хотите спроектировать канал функции (i), который возвращает номер канала для каждого из ваших n интервалов.

Единственное ограничение, которое у вас есть, заключается в том, что никакие два пересекающихся интервала не могут быть на одном канале. Это соответствует неориентированному графу, где ваши интервалы являются вершинами, и между двумя вершинами есть ребро, если и только если соответствующие интервалы пересекаются.

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

Вы хотите найти набор независимых наборов этой формы, где объединение всех их охватывает граф, и они попарно не пересекаются. Вы хотите как можно меньше независимых наборов.

Связанная с этим задача нахождения максимального независимого множества является NP-полной. Поэтому я не думаю, что вы должны ожидать, что найдете алгоритм полиномиального времени для поиска решения, которое дает вам минимальное количество каналов.

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

Для (B) вы можете сделать это:

feasible(M)

    initialize M empty channels (lists of intervals)

    sort intervals by a_i value

    for each interval I = [a_i, b_i):

        insert it into the channel for which the most recent
        interval is closest to the current interval (but not intersecting)

        if I cannot be inserted at the end of any channel, return false

    return true //the M channels are a feasible solution

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

Попробуйте M = 1, 2, 4, 8, 16, ..., пока не дойдете до первого M = 2^k, так что feasible(M) возвращает истину. Затем выполните бинарный поиск между 2^{k - 1} и 2^k, чтобы найти минимум M.