"""Original grouped endpoint sweep for half-open interval coverage."""
from fractions import Fraction as F
from itertools import combinations
import json
def sweep(intervals):
 if type(intervals) is not list or len(intervals)>10:raise ValueError('at most10 intervals')
 ids=[];events={}
 for r in intervals:
  if type(r) is not dict or set(r)!=set(['id','start','end']) or type(r['id']) is not str or not r['id'] or type(r['start']) is not int or type(r['end']) is not int or abs(r['start'])>100 or abs(r['end'])>100 or r['start']>=r['end']:raise ValueError('unique IDs and bounded positive integer interval')
  ids.append(r['id']);events.setdefault(r['start'],{'end':[],'start':[]})['start'].append(r['id']);events.setdefault(r['end'],{'end':[],'start':[]})['end'].append(r['id'])
 if len(ids)!=len(set(ids)):raise ValueError('unique IDs')
 times=sorted(events);active=set();segments=[];trace=[]
 for i,t in enumerate(times):
  before=sorted(active);active.difference_update(events[t]['end']);active.update(events[t]['start']);trace.append({'time':t,'before':before,'ends':sorted(events[t]['end']),'starts':sorted(events[t]['start']),'after':sorted(active)})
  if i+1<len(times):segments.append({'start':t,'end':times[i+1],'active':sorted(active),'count':len(active)})
 assert not active
 return {'events':trace,'segments':segments,'peak':max([x['count'] for x in segments]+[0]),'union_length':sum(x['end']-x['start'] for x in segments if x['active'])}
def oracle(intervals):
 times=sorted({r[k] for r in intervals for k in ['start','end']});segments=[]
 for l,r in zip(times,times[1:]):
  mid=F(l+r,2);active=sorted(x['id'] for x in intervals if x['start']<=mid<x['end']);segments.append({'start':l,'end':r,'active':active,'count':len(active)})
 return segments
def demo():
 rows=[{'id':i,'start':s,'end':e} for i,s,e in [('A',0,3),('B',1,4),('C',3,5),('D',5,6)]];out=sweep(rows);assert out['segments']==oracle(rows) and out['peak']==2 and out['union_length']==6
 t3=next(x for x in out['events'] if x['time']==3);assert t3['after']==['B','C'];closed=sum(x['start']<=3<=x['end'] for x in rows);assert closed==3
 possible=[{'id':str(i),'start':s,'end':e} for i,(s,e) in enumerate(combinations(range(4),2))];checks=0
 for mask in range(64):
  x=[r for i,r in enumerate(possible) if mask&(1<<i)];res=sweep(x);ref=oracle(x);assert res['segments']==ref;assert res['union_length']==sum(r['end']-r['start'] for r in ref if r['count']);assert res['peak']==max([r['count'] for r in ref]+[0]);checks+=1
 extras=[]
 for x in [[],[dict(id='A',start=0,end=1),dict(id='B',start=3,end=4)],[dict(id='A',start=0,end=4),dict(id='B',start=1,end=2)]]:
  result=sweep(x);assert result['segments']==oracle(x);extras.append({'intervals':x,'result':result})
 rejected=[]
 for x in [[dict(id='A',start=1,end=1)],[dict(id='A',start=2,end=1)],[rows[0],rows[0]],[dict(id='A',start=True,end=3)]]:
  try:sweep(x)
  except ValueError:rejected.append(repr(x))
  else:raise AssertionError('expected rejection')
 return {'intervals':rows,'grouped_halfopen_sweep':out,'time3_closed_wrong_for_this_contract':closed,'time3_halfopen_active':t3['after'],'all64_interval_subset_oracles':checks,'extra_gap_nested_empty_cases':extras,'rejected':rejected,'scope':'offline authored integer-time intervals, all retained; no real booking, timezone/DST, capacity benchmark or weighted subset selection'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))