Find missing rectangles

gistfile1.cs

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;

namespace FillEmptySpaceWithRectangles
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            // Defining the problem
            var p = new Problem(300, 113, new[]
                                              {
                                                  new Rectangle(12, 26, 60, 30),
                                                  new Rectangle(12, 62, 60, 30),
                                                  new Rectangle(82, 27, 37, 30),
                                                  new Rectangle(82, 63, 37, 30),
                                                  new Rectangle(159, 11, 60, 30),
                                                  new Rectangle(194, 62, 24, 30),
                                                  new Rectangle(227, 12, 60, 30),
                                                  new Rectangle(227, 62, 60, 30),
                                              });

            IEnumerable<Rectangle> result = Solve(p);

            foreach (var rectangle in result)
            {
                Console.WriteLine(rectangle);
            }
        }

        private static IEnumerable<Rectangle> Solve(Problem problem)
        {
            // Putting all edge coordinates in two sorted lists
            // one for the x coordinates (left, right)
            var interestingXs = new List<int> {0, problem.Width};
            interestingXs.AddRange(problem.Rectangles.Select(x => x.Left));
            interestingXs.AddRange(problem.Rectangles.Select(x => x.Right));
            interestingXs = interestingXs.Distinct().OrderBy(x => x).ToList();

            // one for the y coordinates (top, bottom)
            var interestingYs = new List<int> {0, problem.Height};
            interestingYs.AddRange(problem.Rectangles.Select(x => x.Top));
            interestingYs.AddRange(problem.Rectangles.Select(x => x.Bottom));
            interestingYs = interestingYs.Distinct().OrderBy(x => x).ToList();

            // initialize solution with given rectangles
            var solution = new List<Rectangle>(problem.Rectangles);

            // this is the area of our blue rectangle
            int targetArea = problem.Width * problem.Height;

            // iterating over every possible combination of coordinates
            for (int il = 0; il < interestingXs.Count; il++)
            {
                for (int ir = interestingXs.Count - 1; ir > il; ir--)
                {
                    for (int it = 0; it < interestingYs.Count; it++)
                    {
                        for (int ib = interestingYs.Count - 1; ib > it; ib--)
                        {
                            int left = interestingXs[il];
                            int top = interestingYs[it];
                            int width = interestingXs[ir] - left;
                            int height = interestingYs[ib] - top;

                            var rect = new Rectangle(left, top, width, height);

                            // check if new rectangle intersects with any other of our rectangles
                            if (solution.Any(x => x.IntersectsWith(rect))) continue;

                            // add new rectangle to solution
                            solution.Add(rect);

                            // check if the sum of all rectangle areas equals the area of our problems blue (main) rectangle
                            // return result if it is equal
                            int sum = solution.Sum(x => x.Width*x.Height);
                            if (sum == targetArea) return solution;
                        }
                    }
                }
            }

            throw new Exception("If you ever reach this point something went horribly wrong!");
        }
    }

    internal class Problem
    {
        private readonly int _height;
        private readonly Rectangle[] _rectangles;
        private readonly int _width;

        public Problem(int width, int height, Rectangle[] rectangles)
        {
            _width = width;
            _height = height;
            _rectangles = rectangles;
        }

        public int Height
        {
            get { return _height; }
        }

        public Rectangle[] Rectangles
        {
            get { return _rectangles; }
        }

        public int Width
        {
            get { return _width; }
        }
    }
}

Quite naive solution for the following problem: http://inder-gnu.blogspot.co.at/2012/09/find-missing-rectangles.html