(define-struct request [start stop name])

; See below, for examples of data, and test cases.


;; greedy-sched-v1:
;; Given a list of requests,
;; return a list of requests that can be scheduled.
;;
;; Implementation:
;; Use the greedy algorithm as given in Rosen 5ed, Section 3.3, Example 12:
;; Schedule the first jobs with smallest ending time,
;; and then recur on the other consistent jobs (those
;; whose start-time is >= the stop-time of the job just scheduled.
;;
(define (greedy-sched-v1 reqs)
  (cond [(empty? reqs) empty]
        [else (let* {[stop0  (apply min (map request-stop reqs))]
                     ; Now recover the (well, a) job which stop-time of stop0:
                     [job0   (first (filter (lambda (r) (= stop0 (request-stop r))) reqs))]
                     ; Gather the jobs whose start-time is > the current stop time.
                     [others (filter (lambda (r) (> (request-start r) stop0)) reqs)]}
                (cons job0 (greedy-sched-v1 others)))]))




;; greedy-sched-v2:
;; As greedy-sched-v1, but different implementation.
;;
;; Implementation:
;; We try the dual of v1: select the job with highest start-time,
;; and create a schedule ending with that job.
;; We recur on the still-consistent jobs.
;; This is the dual of v1; does the dual algorithm also happen to work?
;; 
(define (greedy-sched-v2 reqs)
  (cond [(empty? reqs) empty]
        [else (let* {[startN (apply max (map request-start reqs))]
                     ; Now recover the (well, a) job which start-time of stopN:
                     [jobN   (first (filter (lambda (r) (= startN (request-start r))) reqs))]
                     ; Gather the jobs whose stop-time is < the current start time.
                     [others (filter (lambda (r) (< (request-stop r) startN)) reqs)]}
                (append (greedy-sched-v2 others) (list jobN)))]))





;;;;;;;;;;;;;;;;;; Test cases ;;;;;;;;;;;;;;;;;;;;;;;;
;;;
;;; Test cases for greedy-schedule.ss
;;;
;;; (We tacked all this into the source file, for web/download purposes;
;;; really it should be a separate file which loads the code from the source file.

;(load "greedy-schedule.ss") 


(define r1 (make-request 9 17 "schmo day job, 9:00-17:00."))
(define r2 (make-request (+ 10 50/60) (+ 12 05/60) "comp280"))
(define r3 (make-request 0 5 "insomnia"))
(define r4 (make-request 10 10 "quick nap"))


(define (test-a-scheduler sched)
  (and
   ; version 1 of greedy-sched:
   ; No jobs:
   (empty? (sched empty))
   ; one job:
   (equal? (sched (list r1))
           (list r1))
   ; v1, two compatible jobs
   (equal? (sched (list r1 r3))
           (list r3 r1))
   ; two incompatible jobs
   (= 1 (length (sched (list r1 r2))))
   
   
   (equal? (sched (list r1 r2 r3 r4))
           (list r3 r4 r2))
   ))

(test-a-scheduler greedy-sched-v1)
(test-a-scheduler greedy-sched-v2)