tickets.d

import std.stdio;
import std.datetime : Date;
import std.string : strip;
import std.array : split, empty, front, popFront, array;
import std.conv : to;
import std.algorithm : map, sort, swap;

void main()
{
    auto buf = stdin.byLine().map!toInterval().array();
    typeof(buf) ans;
    while (!buf.empty)
    {
        sort(buf);
        ans ~= buf.front;
        buf.popFront();
        auto i = 0;
        while (i < buf.length)
        {
            if (buf[i] & ans[$-1])
            {
                swap(buf[i], buf[$-1]);
                buf.length -= 1;
            }
            i += 1;
        }
    }
    "%(%s %)".writefln(ans.sort!((a, b) => a.tag < b.tag));
    //"%(%s %)".writefln(ans); // original answer
}

struct Interval(Tag)
{
    int fromI, toE;
    Tag tag;
    this (Date fromI, Date toI, Tag tag=Tag.init)
    {
        this.fromI = fromI.dayOfYear() - 1;
        this.toE = toI.dayOfYear();
        this.tag = tag;
    }
    private this(int fromI, int toE)
    {
        this.fromI = fromI;
        this.toE = toE;
    }
    @property bool nonEmpty() const
    {
        return fromI < toE;
    }
    string toString() const
    {
        return tag.to!string();
    }
    int opCmp(ref const Interval i) const
    {
        return this.toE - i.toE;
    }
    bool opBinary(string op)(ref const Interval i) const
        if (op == "&")
    {
        return
            Interval(this.fromI, i.toE).nonEmpty &&
            Interval(i.fromI, this.toE).nonEmpty;
    }
}

auto toInterval(const(char)[] ticket)
{
    auto buf = ticket.strip().split();
    auto country = buf[0].to!string();
    buf = buf[1].split("-");
    return Interval!string(buf[0].toDateOf!2012, buf[1].toDateOf!2012, country);
}

auto toDateOf(int year)(const(char)[] md)
{
    auto buf = md.split("/").map!(to!size_t);
    immutable month = buf[0];
    immutable date = buf[1];
    return Date(year, month, date);
}