IntervalScheduling:GreedyAlgorithmsGreedytemplate.Considerjobsinsomeorder.Takeeachjobprovidedit'scompatiblewiththeonesalreadytaken.breaks earliest start timebreaksshortestintervalbreaksfewestconflicts自自Pagell2026/9/22CS4335DesignandAnalysisofAlgorithms/WANGLusheng
2026 / 9 /22 CS4335 Design and Analysis of Algorithms/WANG Lusheng Page 11
IntervalScheduling:GreedyAlgorithmGreedy algorithm.Consider jobs in increasing order offinish time.Takeeach jobprovidedit's compatiblewiththe onesalreadytaken.Sort jobs by finish times so that fi ≤f2 ..s f.jobs selectedAΦforj=lton(if (job j compatible with A)A-AUj)子return AImplementation. O(n log n). Sorting the n jobs based on f, needs O(nlogn) time.Remember job j*thatwas added lasttoA.. Job j is compatible with A if sj ≥ fj*.Page 122026/9/22CS4335DesignandAnalysisofAlgorithms/WANGLusheng
2026/9/22 CS4335 Design and Analysis of Algorithms/WANG Lusheng Page 12 Sorting the n jobs based on fi needs O(nlog n) time