#! /usr/bin/env python from sys import stdin, stderr, argv from collections import defaultdict from random import randint OPEN = 0 CLOSE = 1 class Event: def __init__(self, pos, type, id): self.pos = pos self.type = type self.id = id def __repr__(self): return '%s%d@%d' % ('[' if self.type == OPEN else ']', self.id, self.pos) def main(): intervals = [] k = int(argv[1]) if len(argv) <= 2: for line in stdin: l, r = line.split() l = float(l) r = float(r) intervals.append((l, r)) else: for i in range(int(argv[2])): while True: l = randint(0, 99999) r = randint(0, 99999) if l < r: break intervals.append((l, r)) print >> stderr, "calculating events..." events = [] for i in range(len(intervals)): l, r = intervals[i] events.append(Event(l, OPEN, i)) events.append(Event(r, CLOSE, i)) print >> stderr, "sorting events..." evs = sorted(events, key=lambda e: e.pos) print >> stderr, "discoinciding events..." d = 0 last = -1 for i in range(len(evs)): p = evs[i].pos p += d if p <= last: p += last - p + 1 d += last - p + 1 evs[i].pos = p last = p print >> stderr, "creating constraints..." active = [] next = len(intervals) constraints = [] for e in evs: if not active: active = [e.id] active_type = e.type else: if active_type == e.type: if len(active) + 1 < k: active.append(e.id) else: constraints.append((active_type, active + [e.id])) active = [] else: xs = range(next, next + (k - len(active))) next += len(xs) constraints.append((active_type, active + xs)) ys = range(next, next + (k - len(xs) - 1)) next += len(ys) constraints.append((CLOSE if active_type == OPEN else OPEN, xs + [e.id] + ys)) active = ys print >> stderr, "%d constraints, %d variables" % (len(constraints), next) print >> stderr, "calculating occurrences..." occur = defaultdict(set) for i in range(len(constraints)): _, c = constraints[i] for id in c: occur[id].add(i) print >> stderr, "calculating graph..." g = defaultdict(list) for edge, [x, y] in occur.iteritems(): g[x].append((y, edge)) g[y].append((x, edge)) print >> stderr, "verifying bipartiteness..." for u in g: cu, _ = constraints[u] for (v, _) in g[u]: cv, _ = constraints[v] if cu == cv: print >> stderr, "internal error: graph not bipartite" exit(1) print >> stderr, "solving edge coloring problem..." coloring = defaultdict(lambda: None) uncolored = set(range(next)) colors = set(range(k)) while uncolored: e = uncolored.pop() u, v = occur[e] c_u = colors - set([coloring[ee] for (x, ee) in g[u]]) c_v = colors - set([coloring[ee] for (x, ee) in g[v]]) cu = c_u.pop() cv = c_v.pop() c = cv path = [] while True: for (nu, eu) in g[u]: if coloring[eu] == c: u = nu path.append(eu) c = cu if c == cv else cv break else: break for edge in path: coloring[edge] = cu if coloring[edge] == cv else cv coloring[e] = cv print >> stderr, "verify edge coloring..." for u in g: cs = set() for (_, eu) in g[u]: cs.add(coloring[eu]) assert(cs == colors) if len(argv) <= 2: def s(x): if x == int(x): return str(int(x)) else: return str(x) for i in range(len(intervals)): l, r = intervals[i] print s(l), s(r), coloring[i] print >> stderr, "verifying..." counts = [0] * k max_d = 0 for ev in events: max_d = max(max_d, abs(max(counts) - min(counts))) if ev.type == OPEN: counts[coloring[ev.id]] += 1 else: counts[coloring[ev.id]] -= 1 if max_d > 1: print >> stderr, "internal error: max_d =", max_d exit(1) main()