Задача на C#, не проходит по требуемому времени

[blueboar2]

Есть следующая задача:

Программисту-фрилансеру Васе Пупкину требуется выполнить n заданий за n дней. У каждого задания известен свой дедлайн, а также его стоимость(то есть, если он не выполняет задание в указанное время, то его работа не оплачивается). Вася настолько крут, что за один день может сделать одно задание. Выполнение задания можно начать с момента 0. Ваша задача определить максимальную прибыль Васи. 

Пример исходных данных:

3
60 2
65 2
70 2

Результат:

135

За два дня Вася успеет решить только две задачи, и он выберет вторую и третью, что даст ему прибыль в 135 единиц.
Эту задачу нужно решить на C# с использованием жадного алгоритма. Мое решение приведено ниже. Вывод времени добавлен с целью контролировать, сколько работает программа, он необязателен. Файл читается по байтам тоже для быстроты. Программа работает правильно, и проходит все тесты, кроме последнего, ибо там 100000 исходных данных, а нужно успеть за секунду. Что еще ускорить я не знаю.

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var y = new List<Tuple<int, int>>();
            var sset = new List<int>();

            Console.WriteLine(DateTime.Now.ToString("h:mm:ss ffff"));

            FileStream fileStream = new FileStream(@"input.txt", FileMode.Open, FileAccess.Read);
            int num = 0;
            int t = fileStream.ReadByte() - 48;
            while (t >= 0)
            {
                num = 10 * num + t;
                t = fileStream.ReadByte() - 48;
            }

            while (t < 0)
            {
                t = fileStream.ReadByte() - 48;
            }

            for (int i = 0; i < num; i++)
            {
                int newcost = 0;
                int newdeadline = 0;

                while (t >= 0)
                {
                    newcost = 10 * newcost + t;
                    t = fileStream.ReadByte() - 48;
                }

                while (t < 0)
                {
                    t = fileStream.ReadByte() - 48;
                }

                while (t >= 0)
                {
                    newdeadline = 10 * newdeadline + t;
                    t = fileStream.ReadByte() - 48;
                }

                if (i != num - 1)
                {
                    while (t < 0)
                    {
                        t = fileStream.ReadByte() - 48;
                    }
                }

                y.Add(Tuple.Create(-newcost, newdeadline));
                sset.Add(i);
            }
            sset.Add(num);
            sset.Add(num + 1);

            y.Sort(Comparer<Tuple<int, int>>.Default);

            Int64 sum = 0;

            for (int i = 0; i < num; i++)
            {
                int lval = 0;
                int uval = sset.Count - 1;

                while ((uval - lval) != 1)
                {
                    int mid = (int)((lval + uval) / 2);
                    int zuval = sset[mid];
                    if (zuval > y[i].Item2) { uval = mid; } else { lval = mid; }
                }

                int xzuval = sset[lval];

                if (xzuval == 0)
                {
                    sset.RemoveAt(sset.Count - 1);
                }
                else
                {
                    sset.RemoveAt(lval);
                    sum = sum - y[i].Item1;
                }
            }

            Console.WriteLine(DateTime.Now.ToString("h:mm:ss ffff"));

            StreamWriter sw = new StreamWriter(@"output.txt");
            sw.WriteLine(sum);
            sw.Close();
        }
    }
}

-- 30.05.2019, 13:17 --

И еще - если на C# быстрее не получится, можно на C++, если будет быстрее, но там я вообще не представляю как.

[Munin]

Как по-вашему, какова алгоритмическая сложность вашего решения? $\mathcal{O}(n)$? $\mathcal{O}(n\log n)$? $\mathcal{O}(n^2)$? Другая?
Почему?

[blueboar2]

Квадратичная, так как есть цикл по всем работам, и внутри есть удаление элемента из списка. Списки в C# это обертки над массивами (а не над двусвязными списками). Так что n*n -> n^2.
Я пробовал заменить массив на LinkedList, но мне нужно обращаться к нему по индексу. Можно в принципе использовать set, но с ним у меня почему-то получилось еще медленнее.

[Munin]

А может быть, можно сделать алгоритм так, чтобы не удалять элементы из списка?

Намёк: сначала вы зачем-то сортируете (другой) массив. Время сортировки $\mathcal{O}(n\log n),$ кстати говоря.

[blueboar2]

Я сортирую другой массив, который содержит дедлайны и стоимость. Так как я использую жадный алгоритм, то мне нужны сначала самые дорогие работы. Это - да, $n\cdot\log(n)$
Но потом, когда я беру самую дорогую работу, и вижу, что ее нужно сделать, например до дня №7, мне нужно отметить, что мой день №6 теперь занят. Для этого я удаляю из второго массива, в котором просто числа от 1 до N (количества работ) нужное число.

[Munin]

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

[blueboar2]

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

[Munin]

blueboar2 в сообщении #1396612 писал(а):

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

Объясните поподробней.

[blueboar2]

Ну например, у нас десять работ. Первая стоимостью 2 рубля, должна быть сделана в первый день. Восемь работ стоимостью 100 единиц, до пятого дня, и одна, 2 рубля, до десятого. Если мы отсортируем массив по дедлайну по возрастанию, то получим сначала первую работу, потом 2-9, потом десятую. Возьмем первую в первый день, вторую во второй, третью в третий, четвертую в четвертый, пятую в пятый. Дальше десятую в любой после этого. Итого 404 рубля.

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

[Munin]

blueboar2 в сообщении #1396617 писал(а):

Если мы отсортируем массив по дедлайну по возрастанию

...а если как-то иначе?

-- 30.05.2019 15:57:31 --

Вот например, по стоимости вы сортируете по убыванию.

[blueboar2]

Хорошо, я вас понял, кажется. Я правильно понимаю, что если бы дней было n, а работ 2n, то этот алгоритм не сработал бы?

[Munin]

Ну, это уже не знаю.

[mihaild]

blueboar2 в сообщении #1396639 писал(а):

Я правильно понимаю, что если бы дней было n, а работ 2n, то этот алгоритм не сработал бы?

Какой алгоритм-то?

Вообще полезно оценивать асимптотику работы и сопоставлять её с размером входа. Если время работы $O(n^2)$, то на входе размера $10^5$ по времени почти наверняка не пройдёт, надо быстрее.

Ваш алгоритм можно улучшить, если заменить sset на что-то, поддерживающее поиск максимального элемента, меньшего данного, и удаление элемента за логарифм (в C++ это умеет std::set, не знаю, есть ли аналоги в C#). А можно полностью переделать - тоже понадобится некоторая нетривиальная структура данных, но гораздо более простая, чем деревья.

[photon]

(Оффтоп)

blueboar2 в сообщении #1396541 писал(а):

Вася настолько крут, что за один день может сделать одно задание.

blueboar2 в сообщении #1396541 писал(а):

ибо там 100000 исходных данных

А Вася и правда крут - 270 лет работать без выходных не каждый сможет.

-- Thu May 30, 2019 17:31:43 --

Значения дедлайнов целочисленны и не так уж велики ($100000$ - вполне терпимая длина массива), так что по дедлайну можно отсортировать за $\mathcal{O}(n)$

[_Ivana]

Что-нибудь типа такого

Используется синтаксис Haskell

import Data.List

rp :: String -> (Int, Int)
rp = (\[x,y] -> (- read x, read y)) . words

main = getContents >>= print . fst . foldl' (\(s,i) (a,d) -> if i>=d then (s,i) else (s-a, i+1)) (0,0) . sort . map rp . tail . lines
 

Жаль не гуглится сайт с задачкой (хотя всякие Хабры и Ленты с матроидами гуглятся отлично), не могу проверить на реальных тестах