Solution of the codingame contest ("Supercomputer")

Here is a task to solve
http://www.codingame.com/ide/?target=clogin&s=1&id=17491280f2d98642c3d6e78f43fc45ddc2c57f#!test:192829:true:%2523!list

In the Computer2000 data center, you are responsible for planning the usage of a supercomputer for scientists.

​Therefore you've decided to organize things a bit by planning everybody’s tasks. The logic is simple: the higher the number of calculations which can be performed, the more people you can satisfy.

Scientists give you the starting day of their calculation and the number of consecutive days they need to reserve the calculator.

For example:

Calculation	Starting Day	Duration
A	2	5
B	9	7
C	15	6
D	9	3

• Calculation A starts on day 2 and ends on day 6
• Calculation B starts on day 9 and ends on day 15
• Calculation starts on day 15 and ends on day 20
• Calculation D starts on day 9 and ends on day 11

In this example, it’s not possible to carry out all the calculations because the periods for B and C overlap. 3 calculations maximum can be carried out: A, D and C. . 

INPUT:

Line 1: The number N of calculations

The N following lines: on each line, the starting day J and the duration D of reservation, separated by a blank space.

OUTPUT:

The maximum number of calculations that can be carried out.

CONSTRAINTS:

0 < N < 100000

0 < J < 1000000

0 < D < 1000

EXAMPLE :

Input

4

2 5

9 7

15 6

9 3

Output

3

Input

5

3 5

9 2

24 5

16 9

11 6

Output

4

---

Available RAM : 512MB

Timeout: 1 seconds

• The program has to read inputs from standard input
• The program has to write the solution to standard output
• The program must run in the test environment

Download the files provided in the test script:

Example 1: in1.txt out1.txt

Example 2: in2.txt out2.txt

Large number of scientists: in3.txt out3.txt

Proposed Solution in C#

class TaskSuperComputer
    {
        public int N { get; set; }
        List<Calculation> inputItems = new List<Calculation>();

        public void Run()
        {
            using (new ConsoleManager("Test_3_input.txt", "Test_3_outputMy.txt"))
            {
                GetData();

                if (inputItems.Count <= 1) Console.WriteLine(inputItems.Count);
                else
                {
                    inputItems = inputItems.OrderBy(c => c.Start).ToList(); // sort by start
                    Calculate(inputItems);
                }
            }
        }

        void Calculate(List<Calculation> items)
        {
            int[] max = new int[items.Count];
            for (int i = 0; i < items.Count; i++)
            {
                var cur = items[i];
                max[i] = 1;
                for (int j = i - 1; j >= 0; j--)
                {
                    var prev = items[j];
                    //if (cur.Start > prev.End)
                    if (cur.NonConflictsWith(prev))
                    {
                        if (max[i] < max[j] + 1)
                        {
                            max[i] = max[j] + 1;
                            break;
                        }
                    }
                }
                Debug.Print("I = {0} MAX = {1}", i, max[i]);
            }
            Console.WriteLine(max[items.Count - 1]);

        }

        void RemoveMaxConflict(List<Calculation> items)
        {
            var conflictingNumbers = (from c in items select c.GetNumberConflicting(items)).ToList();
            Debug.Print("Conflicting counters: " + conflictingNumbers.Print());

            int max = conflictingNumbers.Max();
            if (max == 0) Console.WriteLine(items.Count); // final result
            else
            {
                int index = conflictingNumbers.FindIndex(n => n == max);
                if (index > 0)
                {
                    items.RemoveAt(index);
                    Debug.Print("Remove I = {0} MAX = {1}", index, max);
                    RemoveMaxConflict(items);
                }
            }
        }

        void GetData()
        {
            string line = Console.ReadLine();
            N = Convert.ToInt32(line);
            for (int i = 0; i < N; i++)
            {
                line = Console.ReadLine();
                var arr = line.Split(' ');
                inputItems.Add(new Calculation(int.Parse(arr[0]), int.Parse(arr[1])));
            }
            Debug.Print("N =" + N + "; " + inputItems.Print());
        }
    }

    class Calculation
    {
        public int Start { get; set; }
        public int Duration { get; set; }
        public int End { get; set; }

        public Calculation(int s, int d)
        {
            Start = s;
            Duration = d;
            End = s + d - 1;
        }

        public bool NonConflictsWith(Calculation that)
        {
            if (Object.ReferenceEquals(this, that)) return true;
            bool ok = (that.End < Start || that.Start > End);
            if (ok) Debug.Print("{0} not conflicts with {1}", this, that);
            else Debug.Print("{0} CONFLICTS with {1}", this, that);
            return ok;
        }

        public bool ConflictsWith(Calculation that)
        {
            bool ok = !NonConflictsWith(that);
            return ok;
        }

        public override string ToString()
        {
            return "(" + Start + "," + End + ")";
        }

        public int GetNumberNonConflicting(List<Calculation> items)
        {
            int counter = items.Count(c => this.NonConflictsWith(c));
            Debug.Print("{0}:  GetNumberNonConflicting = {1}", this, counter);
            return counter;
        }
        public int GetNumberConflicting(List<Calculation> items)
        {
            int counter = (from i in items where i.Start >= Start && i.Start <= End || i.End >= Start && i.End <= End select i).Count() - 1;
            //int counter = items.Count(c => this.ConflictsWith(c));

            Debug.Print("{0}:  GetNumberConflicting = {1}", this, counter);
            return counter;
        }
    }

    static class PrintHelper
    {
        public static string Print<T>(this List<T> items)
        {
            return string.Join(" ", items.Select(i => i.ToString()).ToArray());
        }
    }