Задача(у меня не совсем такая, она на другом языке, так что я просто привожу подобную).
Даны n
заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия si и fi для i
-й заявки). В случае пересечения заявок можно удовлетворить лишь одну из них. Заявки с номерами i
и j
совместны, если интервалы (si,fi) и (sj,fj) не пересекаются (то есть fi < fj или fj < fi). Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.
Количество заявок и сами заявки в текстовом документе prednasky.in, то-есть:
Ввод (текстовый документ):
5 - первая строчка - кол-во интервалов
2 4 (2 - начало интервала, 4 - конец и тд)
1 7
6 9
9 11
5 8
Вывод:
3 (максимальное количество совместных друг с другом заявок)
1 5 4 (номера этих заявок(если есть несколько вариантов - выписать любой))
Программу проверяет специальный сайт с тестами, и моя программа не проходит тесты на больших числах, хотя, как мне кажется я добился временной сложности nlogn+n (с памятью всё уже нормально, именно по скорости не проходит). Вот сам код:
class Program
{
static int N;
static int[,] a;
static void Main(string[] args)
{
using (StreamReader sr = new StreamReader(@"prednasky.in"))
{
string line;
line = sr.ReadLine();
N = int.Parse(line);
a = new int[N, 2];
int[] indx = new int[N];
int[] b = new int[N];
for (int i = 0; i < N; i++)
{
line = sr.ReadLine();
int[] nums = line.Trim().Split().Select(w => int.Parse(w)).ToArray();
//начало интервалов и их идексы записываем в массив А
a[i, 0] = nums[0];
a[i, 1] = i + 1;
//Концы интервалов записываем в массив б
b[i] = nums[1];
//заполняем массив индексов;
indx[i] = i;
}
//Cортировка массива индексов по массиву б
Array.Sort(b, indx);
//Дальше одним циклом проходим массив а, но не по i, а по полю индексов (для того, что бы не сортировать двумерный массив, геморно же, лучше одномерный))
//string str = "";
int last = 0;
int poc = 0;
for (int i = 0; i < N; i++)
{
if (a[indx[i], 0] > last)
{
//в самое начало "отсортированного" массива записываем нужные числа по порядку
a[indx[poc], 0] = a[indx[i], 1];
poc++;
last = b[i];
}
}
using (StreamWriter sr1 = new StreamWriter(@"rozvrh.out"))
{
sr1.WriteLine(poc);
for (int i = 0; i < poc; i++)
{
sr1.Write(a[indx[i], 0]);
sr1.Write(" ");
}
}
}
}
}
Алгоритм работает, проблема только со скоростью. Любым идеям буду рад)