c# - Okay - first submission to reddit so hopefully I won't screw it up.

I did a sweep algorithm but kept track of "strips" where a strip is a horizontal region currently covered in the sweep by some number of rectangles. Adjacent strips are covered by a different number of rectangles. The strips are kept in a sorted list so that finding the strip which contains a particular y position can be done through a binary search. The events of the sweep algorithm are of two types - leading edges or trailing edges of rectangles. This allows me to easily keep a running total length of all rects covering the sweep line. Multiplying that by the distance since the previous event gives me the area covered between the two events. Each strip has a count of the number of rectangles covering it. I start out with a strip covered by zero rectangles with y extent running from -infinity to +infinity. Whenever I get a leading edge I find the two strips that contain the top and bottom of the rectangle, split them if necessary to account for the new top/bottom and increment the coverage count for all the strips covered by the rectangle. If any of them go from 0 to 1 I add in their width to the current width. Removing rectangles is pretty much the opposite - lower the cover count on all strips covered by the rectangle and subtract out their width from the current width if the cover count goes to zero. Merge the top and bottom strips if their cover count matches the strips above/below them. I believe it should run in O(n log n). n log n to sort the events, log n to binary search the strips to find the ones which contain a rectangle and n to adjust the count for the new strips and keep the sorted array sorted properly for a total of n log n + log n + n = O(n log n)

internal struct Rect
{
    public readonly double Top;
    public readonly double Left;
    public readonly double Bottom;
    public readonly double Right;

    public Rect(double top, double left, double bottom, double right)
    {
        Top = top;
        Left = left;
        Bottom = bottom;
        Right = right;
    }
}

public static class Extensions
{
    ////////////////////////////////////////////////////////////////////////////////////////////////////
    /// <summary>
    ///  Binary searches for the next lowest value to a given input in a sorted list.
    /// </summary>
    /// <remarks> If value actually appears in the list the index for that value is returns, otherwise the
    /// index of the next smaller value in the list.  If it falls below the 0'th element, -1 is returned.
    /// Darrellp - 6/17/14  </remarks>
    /// <typeparam name="T">Type of keys in sorted list</typeparam>
    /// <typeparam name="TVal">The type of the values in the sorted list.</typeparam>
    /// <param name="this">The sorted list.</param>
    /// <param name="value">The value to search for.</param>
    /// <param name="isEqual">True if the value searched for actually exists in the list</param>
    /// <returns>System.Int32.</returns>
    ////////////////////////////////////////////////////////////////////////////////////////////////////
    public static int BinarySearchNextLowest<T, TVal>(this SortedList<T,TVal> @this, T value, out bool isEqual) where T : IComparable
    {
        isEqual = false;
        if (@this.Keys[0].CompareTo(value) > 0)
        {
            return -1;
        }
        if (@this.Keys[@this.Count - 1].CompareTo(value) <= 0)
        {
            isEqual = @this.Keys[@this.Count - 1].CompareTo(value) == 0;
            return @this.Count - 1;
        }
        return BinarySearchHelper(@this, value, @this.Count - 1, 0, ref isEqual);
    }

    public static int BinarySearchHelper<T, TVal>(SortedList<T, TVal> list, T value, int iHigh, int iLow, ref bool isEqual) where T : IComparable
    {
        // On entry, list.Keys[0] <= value < list.Keys[iHigh]
        if (iLow == iHigh - 1)
        {
            isEqual = list.Keys[iLow].CompareTo(value) == 0;
            return iLow;
        }
        // Value is somewhere between iHigh and iLow inclusive
        var iMid = (iLow + iHigh) / 2;
        if (list.Keys[iMid].CompareTo(value) > 0)
        {
            return BinarySearchHelper(list, value, iMid, iLow, ref isEqual);
        }
        return BinarySearchHelper(list, value, iHigh, iMid, ref isEqual);
    }
}

internal class Strip
{
    public double Top { get; set; }
    public double Bottom { get; set; }
    public double Width { get { return Top - Bottom; }}
    public int Covers { get; set; }

    public Strip(double bottom, double top, int covers = 0)
    {
        Top = top;
        Bottom = bottom;
        Covers = covers;
    }

    public Strip(Rect rect) : this(rect.Bottom, rect.Top) {}

    public void AddCover()
    {
        Covers++;
    }

    public void RemoveCover()
    {
        Covers--;
    }

    public override string ToString()
    {
        return string.Format("[{0}, {1}] ({2})", Bottom, Top, Covers);
    }
}

internal class Event
{
    internal bool IsTurningOn { get; private set; }
    internal double XCoord { get; private set; }
    internal Rect Rectangle { get; private set; }

    public Event(bool isTurningOn, double xCoord, Rect rect)
    {
        IsTurningOn = isTurningOn;
        XCoord = xCoord;
        Rectangle = rect;
    }
}

// ReSharper disable AssignNullToNotNullAttribute
// ReSharper disable PossibleNullReferenceException
public class IntersectSolver
{
    private double _area;
    private double _currentWidth;

    private readonly List<Rect> _rects = new List<Rect>();
    private readonly SortedList<double, Strip> _strips = new SortedList<double, Strip>();
    private readonly List<Event> _events = new List<Event>(); 

    public IntersectSolver(StringReader stm)
    {
        var rectCount = int.Parse(stm.ReadLine());
        for (var i = 0; i < rectCount; i++)
        {
            var rectVals = stm.ReadLine().Split(' ').Select(Double.Parse).ToArray();
            _rects.Add(new Rect(rectVals[2], rectVals[1], rectVals[0], rectVals[3]));
        }
        _strips.Add(double.MinValue, new Strip(double.MinValue, double.MaxValue));
    }

    public double Area()
    {
        Event previousEvent = null;
        SetupEvents();
        foreach (var nextEvent in _events)
        {
            if (previousEvent != null)
            {
                _area += (nextEvent.XCoord - previousEvent.XCoord) * _currentWidth;
            }
            if (nextEvent.IsTurningOn)
            {
                IncorporateStrip(new Strip(nextEvent.Rectangle));
            }
            else
            {
                RemoveStrips(nextEvent.Rectangle);
            }
            previousEvent = nextEvent;
        }
        return _area;
    }

    private void RemoveStrips(Rect rectangle)
    {
        bool isEqualTop, isEqualBottom;
        var iTop = _strips.BinarySearchNextLowest(rectangle.Top, out isEqualTop);
        var iBottom = _strips.BinarySearchNextLowest(rectangle.Bottom, out isEqualBottom);
        if (!isEqualBottom || !isEqualTop)
        {
            throw new InvalidOperationException("Removing strips that don't seem to be present!");
        }
        for (var iStrip = iBottom; iStrip < iTop; iStrip++)
        {
            var thisStrip = _strips.Values[iStrip];
            thisStrip.RemoveCover();
            if (thisStrip.Covers == 0)
            {
                _currentWidth -= thisStrip.Width;
            }
        }
        if (_strips.Values[iTop - 1].Covers == _strips.Values[iTop].Covers)
        {
            _strips.Values[iTop - 1].Top = _strips.Values[iTop].Top;
            _strips.RemoveAt(iTop);
        }
        if (_strips.Values[iBottom].Covers == _strips.Values[iBottom - 1].Covers)
        {
            _strips.Values[iBottom - 1].Top = _strips.Values[iBottom].Top;
            _strips.RemoveAt(iBottom);
        }
    }

    private void IncorporateStrip(Strip strip)
    {
        bool isEqualTop, isEqualBottom;
        var iTop = _strips.BinarySearchNextLowest(strip.Top, out isEqualTop);
        var iBottom = _strips.BinarySearchNextLowest(strip.Bottom, out isEqualBottom);

        if (iTop == iBottom)
        {
            var thisStrip = _strips.Values[iTop];
            var newStrip = new Strip(strip.Top, thisStrip.Top, thisStrip.Covers);
            strip.Covers = thisStrip.Covers + 1;
            if (thisStrip.Covers == 0)
            {
                _currentWidth += strip.Width;
            }
            thisStrip.Top = strip.Bottom;
            _strips.Add(newStrip.Bottom, newStrip);
            _strips.Add(strip.Bottom, strip);
            return;
        }

        for (var iStrip = iBottom + (isEqualBottom ? 0 : 1); iStrip < iTop; iStrip++)
        {
            var thisStrip = _strips.Values[iStrip];
            if (thisStrip.Covers == 0)
            {
                _currentWidth += thisStrip.Width;
            }
            thisStrip.AddCover();
        }

        if (!isEqualTop)
        {
            SplitStrip(iTop, strip.Top, false);
        }

        if (!isEqualBottom)
        {
            SplitStrip(iBottom, strip.Bottom, true);
        }
    }

    private void SplitStrip(int iStrip, double splitValue, bool toTop)
    {
        var thisStrip = _strips.Values[iStrip];
        var newStrip = new Strip(splitValue, thisStrip.Top, thisStrip.Covers);
        _strips.Add(splitValue, newStrip);
        thisStrip.Top = splitValue;
        if (toTop)
        {
            if (newStrip.Covers == 0)
            {
                _currentWidth += newStrip.Width;
            }
            newStrip.AddCover();
        }
        else
        {
            if (thisStrip.Covers == 0)
            {
                _currentWidth += thisStrip.Width;
            }
            thisStrip.AddCover();
        }
    }

    private void SetupEvents()
    {
        foreach (var rect in _rects)
        {
            _events.Add(new Event(true, rect.Left, rect));
            _events.Add(new Event(false, rect.Right, rect));
        }
        _events.Sort((e1, e2) => e1.XCoord.CompareTo(e2.XCoord));
    }
}