いくつかの時間間隔を表すソートされていない整数のペアがあります（最初の数値は常に2番目の数値よりも小さくなります）。問題は、チャネル番号 (0..x) と呼ばれる整数を各時間間隔に割り当てて、衝突しない間隔が同じチャネルを共有するようにすることです。可能な限り少ない数のチャネルを使用する必要があります。
たとえば、これらの間隔は 2 つのチャネルを使用します。
50 100 //1
10 70 //0
80 200 //0
入力を最初の列でソートするためにカウントソートを使用して実装し、次に線形検索を使用して、互いに続くペアのチェーンを見つけました。また、最初に入力 *const* 配列を新しい配列にコピーし、最後に入力配列の正しい位置に値を割り当てます。
はい、それは私が大学から受け取った課題であり、すでに実装されていますが、コードを高速化する方法を誰か教えてもらえますか? ペアの並べ替え、チェーン化が可能な限り高速になるように、どのアルゴリズムを使用しますか? 入力配列の長さは最大 1,000 万要素です。
コードは次のとおりです。
#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;
}