C# greedy algorithm to pick activities that do not clash with each other (corrected)

Question

My task is the greedy algorithm:

The activity selection problem is characteristic to this class of problems, where the goal is to pick the maximum number of activities that do not clash with each other.

Sample input (the first line indicates the number of intervals; each subsequent line contains a start time and end time):

5
2 4
1 7
6 9
9 11
5 8

Corresponding output (maximum number of non-overlapping activities, followed by the indexes of those activities):

3
1 5 4

The output above indicates that the activities at time intervals 2-4, 5-8, and 9-11 can all be chosen with no overlap.

The program works on small data, but it is too slow for really big input and I don't know how to improve it. Any ideas?

  class Program
{       
    static void Main(string[] args)

    {
       int N;
       int[,] a;
        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(int.Parse).ToArray();
                //the beginning of the interval to a[i, 0], indexes to a[i, 1]
                a[i, 0] = nums[0];
                a[i, 1] = i + 1;
                //The end of the interval to b[i]
                b[i] = nums[1];
                //indx is array of indexes, i sort it instead of array a
                indx[i] = i;
            }

            //now sort array of the end of the interval and array of indexes by it
            Array.Sort(b, indx);
            //now in 1 cycle going through a[index, *] and b. And save "correct" intervals to the start of a(becouse we already don't need it         

            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(" ");
                }
                }
        }
    }

}

Answer 1

One of the prevailing rules of C# code development is that your code should be readable by others. That means the intent of what you are doing should be easily determined by someone else reading your code.

This is not the case with your post.

I can't even begin to comment upon your algorithm without taking lots of time to figure out what you are doing. Therefore, my reply is about style and structure.

Don't put everything in Main(). Your app wants to do 3 overall things:

1. Read inputs
2. Run thru a calculation
3. Write outputs

Your Main() would be simplified along those division of duties. Thus your new Main() would:

1. Call the method that reads and validates inputs
2. Call the method performing calculations based on the validated inputs
3. Call the method performing outputs

Choose better names for your objects. a, b, and indx tell me little and are hard to follow. Especially with indx and this notion of pointing to an indx. C# has wonderfully modern features like classes. Something like:

public class Interval
{
    public int Start { get; set; }
    public int End { get; set; }
}

Ditch using pointers to another array. I see no reason to use a[indx[i], 0]. In conjunction with using a class or struct, there's no reason to have a multi-dimensional array.

Imagine how easy it would be to follow your logic that instead of cryptically using:

last = b[i];

Where it's easy to get lost on b[i] and wonder what last means (e.g. does it mean last element in the array or last value you worked with), that you could instead have a List<Interval> (or if you insist Interval[]) in a variable named intervals and you could use:

largestEnd = intervals[i].End;

It's much easier for someone to follow what you mean. And once they can follow that, they will be better positioned to comment on the algorithm.