The earliest start took the longest job

# Self-authored for the EML case corpus (no external origin). A booking system
# fills a single room by taking requests in order of start time, never
# double-books, and every request it takes is a real, valid one. How many
# requests that rule can fit, against how many the room could hold, is computed
# below.
#
# The rule is careful. It reads the real request list; it sorts exactly by start
# time; it never accepts a request that overlaps one already taken; and the
# intent is exactly 'fit as many requests as possible'.
#
# The request that starts first runs all day, and taking it excludes every short
# request behind it - so the earliest-start rule fits one booking where the
# earliest-finish rule fits three.

1 => job_a_start
10 => job_a_end
2 => job_b_start
3 => job_b_end
4 => job_c_start
5 => job_c_end
6 => job_d_start
7 => job_d_end

1 => jobs_taken_by_earliest_start
3 => jobs_taken_by_earliest_finish
jobs_taken_by_earliest_finish - jobs_taken_by_earliest_start => bookings_left_on_the_table
job_a_end - job_a_start => hours_the_first_starter_holds
int(jobs_taken_by_earliest_start * 10000 / jobs_taken_by_earliest_finish) => share_of_the_optimum_per_myriad

"requests (start to end)         : A " + str(job_a_start) + "-" + str(job_a_end) + ", B " + str(job_b_start) + "-" + str(job_b_end) + ", C " + str(job_c_start) + "-" + str(job_c_end) + ", D " + str(job_d_start) + "-" + str(job_d_end) ^0
"earliest start first            : takes A, which overlaps B, C and D" ^0
"bookings by earliest start      : " + str(jobs_taken_by_earliest_start) ^0
"earliest finish first           : takes B, then C, then D" ^0
"bookings by earliest finish     : " + str(jobs_taken_by_earliest_finish) ^0
"bookings left on the table      : " + str(bookings_left_on_the_table) ^0
"share of the optimum reached    : " + str(share_of_the_optimum_per_myriad) + " per ten thousand" ^0
"" ^0

# ---- what the rule verified ----

"the earliest-start rule" ^0
"  reads : the real request list" ^0
"  sorts : exactly by start time" ^0
"  overlap : never accepts a request over one already taken" ^0
"  intent : fit as many requests as possible" ^0
"  double-bookings : 0" ^0
"  verdict : THE ROOM IS BOOKED ALL DAY" ^0
"" ^0
"  never double-booking and honouring the sort exactly is" ^0
"  the part done right here, and it is why every accepted" ^0
"  booking is valid" ^0
"" ^0

# ---- what starting first commits you to ----

"the greedy choice" ^0
"  the first request by start : A, " + str(hours_the_first_starter_holds) + " hours long" ^0
"  what taking A excludes : B, C and D, all inside A's span" ^0
"  what the room could have held : B, C and D, three" ^0
"    bookings in the same hours" ^0
"  what 'earliest start' optimises : who asked first, not how" ^0
"    much of the day is left after them" ^0
"  what 'earliest finish' optimises : how soon the room is" ^0
"    free again - the thing that lets more fit" ^0
"" ^0

# ---- what the room got ----

"the day" ^0
"  bookings : " + str(jobs_taken_by_earliest_start) + " of a possible " + str(jobs_taken_by_earliest_finish) ^0
"  requests turned away that could have fit : " + str(bookings_left_on_the_table) ^0
"  is any accepted booking invalid : no" ^0
"  is the accepted set the largest valid set : no; it is the" ^0
"    set the sort order happened to produce" ^0
"" ^0

# ---- null control ----

# The same requests taken in order of finish time, which is the greedy order
# that does maximise the count.
1 => nc_bookings_by_earliest_start
3 => nc_bookings_by_earliest_finish
2 => nc_bookings_the_right_order_recovers

"null control - sort by finish time instead of start time" ^0
"  bookings, earliest start : " + str(nc_bookings_by_earliest_start) ^0
"  bookings, earliest finish : " + str(nc_bookings_by_earliest_finish) ^0
"  bookings the right order recovers : " + str(nc_bookings_the_right_order_recovers) ^0
"  no request changed; the greedy rule stopped optimising" ^0
"  the wrong quantity" ^0
"" ^0

# ---- the rule ----

"what an earliest-start-first booking rule guarantees" ^0
"  every accepted booking is valid and none overlap :" ^0
"    exactly, real requests, exact sort, no double-booking" ^0
"  the room holds as many bookings as it could : not" ^0
"    addressed; the earliest starter runs " + str(hours_the_first_starter_holds) + " hours and taking" ^0
"    it excludes three that would have fit - " + str(jobs_taken_by_earliest_start) + " booking" ^0
"    where " + str(jobs_taken_by_earliest_finish) + " were possible" ^0
"" ^0

"a greedy rule is only as good as the quantity it greeds for; sorting by who" ^0
"starts first fills the room with whoever asked first, and the request that" ^0
"asked first is the one that leaves least of the day to anyone else" ^0
"" ^0

"It takes requests strictly by start time and never double-books - every" ^0
"accepted booking is valid. But the earliest starter holds the room for " + str(hours_the_first_starter_holds) ^0
"hours and excludes three that would have fit, so the room holds " + str(jobs_taken_by_earliest_start) + " booking" ^0
"where " + str(jobs_taken_by_earliest_finish) + " were possible, " + str(share_of_the_optimum_per_myriad) + " per ten thousand of the optimum, until the sort is by finish." ^0

job_a_start = 1
job_a_end = 10
job_b_start = 2
job_b_end = 3
job_c_start = 4
job_c_end = 5
job_d_start = 6
job_d_end = 7
jobs_taken_by_earliest_start = 1
jobs_taken_by_earliest_finish = 3
bookings_left_on_the_table = jobs_taken_by_earliest_finish - jobs_taken_by_earliest_start
hours_the_first_starter_holds = job_a_end - job_a_start
share_of_the_optimum_per_myriad = int(jobs_taken_by_earliest_start * 10000 / jobs_taken_by_earliest_finish)
print("requests (start to end)         : A " + str(job_a_start) + "-" + str(job_a_end) + ", B " + str(job_b_start) + "-" + str(job_b_end) + ", C " + str(job_c_start) + "-" + str(job_c_end) + ", D " + str(job_d_start) + "-" + str(job_d_end))
print("earliest start first            : takes A, which overlaps B, C and D")
print("bookings by earliest start      : " + str(jobs_taken_by_earliest_start))
print("earliest finish first           : takes B, then C, then D")
print("bookings by earliest finish     : " + str(jobs_taken_by_earliest_finish))
print("bookings left on the table      : " + str(bookings_left_on_the_table))
print("share of the optimum reached    : " + str(share_of_the_optimum_per_myriad) + " per ten thousand")
print("")
print("the earliest-start rule")
print("  reads : the real request list")
print("  sorts : exactly by start time")
print("  overlap : never accepts a request over one already taken")
print("  intent : fit as many requests as possible")
print("  double-bookings : 0")
print("  verdict : THE ROOM IS BOOKED ALL DAY")
print("")
print("  never double-booking and honouring the sort exactly is")
print("  the part done right here, and it is why every accepted")
print("  booking is valid")
print("")
print("the greedy choice")
print("  the first request by start : A, " + str(hours_the_first_starter_holds) + " hours long")
print("  what taking A excludes : B, C and D, all inside A's span")
print("  what the room could have held : B, C and D, three")
print("    bookings in the same hours")
print("  what 'earliest start' optimises : who asked first, not how")
print("    much of the day is left after them")
print("  what 'earliest finish' optimises : how soon the room is")
print("    free again - the thing that lets more fit")
print("")
print("the day")
print("  bookings : " + str(jobs_taken_by_earliest_start) + " of a possible " + str(jobs_taken_by_earliest_finish))
print("  requests turned away that could have fit : " + str(bookings_left_on_the_table))
print("  is any accepted booking invalid : no")
print("  is the accepted set the largest valid set : no; it is the")
print("    set the sort order happened to produce")
print("")
nc_bookings_by_earliest_start = 1
nc_bookings_by_earliest_finish = 3
nc_bookings_the_right_order_recovers = 2
print("null control - sort by finish time instead of start time")
print("  bookings, earliest start : " + str(nc_bookings_by_earliest_start))
print("  bookings, earliest finish : " + str(nc_bookings_by_earliest_finish))
print("  bookings the right order recovers : " + str(nc_bookings_the_right_order_recovers))
print("  no request changed; the greedy rule stopped optimising")
print("  the wrong quantity")
print("")
print("what an earliest-start-first booking rule guarantees")
print("  every accepted booking is valid and none overlap :")
print("    exactly, real requests, exact sort, no double-booking")
print("  the room holds as many bookings as it could : not")
print("    addressed; the earliest starter runs " + str(hours_the_first_starter_holds) + " hours and taking")
print("    it excludes three that would have fit - " + str(jobs_taken_by_earliest_start) + " booking")
print("    where " + str(jobs_taken_by_earliest_finish) + " were possible")
print("")
print("a greedy rule is only as good as the quantity it greeds for; sorting by who")
print("starts first fills the room with whoever asked first, and the request that")
print("asked first is the one that leaves least of the day to anyone else")
print("")
print("It takes requests strictly by start time and never double-books - every")
print("accepted booking is valid. But the earliest starter holds the room for " + str(hours_the_first_starter_holds))
print("hours and excludes three that would have fit, so the room holds " + str(jobs_taken_by_earliest_start) + " booking")
print("where " + str(jobs_taken_by_earliest_finish) + " were possible, " + str(share_of_the_optimum_per_myriad) + " per ten thousand of the optimum, until the sort is by finish.")

requests (start to end)         : A 1-10, B 2-3, C 4-5, D 6-7
earliest start first            : takes A, which overlaps B, C and D
bookings by earliest start      : 1
earliest finish first           : takes B, then C, then D
bookings by earliest finish     : 3
bookings left on the table      : 2
share of the optimum reached    : 3333 per ten thousand

the earliest-start rule
  reads : the real request list
  sorts : exactly by start time
  overlap : never accepts a request over one already taken
  intent : fit as many requests as possible
  double-bookings : 0
  verdict : THE ROOM IS BOOKED ALL DAY

  never double-booking and honouring the sort exactly is
  the part done right here, and it is why every accepted
  booking is valid

the greedy choice
  the first request by start : A, 9 hours long
  what taking A excludes : B, C and D, all inside A's span
  what the room could have held : B, C and D, three
    bookings in the same hours
  what 'earliest start' optimises : who asked first, not how
    much of the day is left after them
  what 'earliest finish' optimises : how soon the room is
    free again - the thing that lets more fit

the day
  bookings : 1 of a possible 3
  requests turned away that could have fit : 2
  is any accepted booking invalid : no
  is the accepted set the largest valid set : no; it is the
    set the sort order happened to produce

null control - sort by finish time instead of start time
  bookings, earliest start : 1
  bookings, earliest finish : 3
  bookings the right order recovers : 2
  no request changed; the greedy rule stopped optimising
  the wrong quantity

what an earliest-start-first booking rule guarantees
  every accepted booking is valid and none overlap :
    exactly, real requests, exact sort, no double-booking
  the room holds as many bookings as it could : not
    addressed; the earliest starter runs 9 hours and taking
    it excludes three that would have fit - 1 booking
    where 3 were possible

a greedy rule is only as good as the quantity it greeds for; sorting by who
starts first fills the room with whoever asked first, and the request that
asked first is the one that leaves least of the day to anyone else

It takes requests strictly by start time and never double-books - every
accepted booking is valid. But the earliest starter holds the room for 9
hours and excludes three that would have fit, so the room holds 1 booking
where 3 were possible, 3333 per ten thousand of the optimum, until the sort is by finish.

Trace event types