29:null 2a:["$","title",null,{"children":"Job Scheduling Problem | Di Wu | Observable"}] 2f:T8c2,original_chart = { const svg = d3.select(DOM.svg(width, height)); var axis = svg.append('g') .call(xAxis); axis.selectAll('.tick line').attr("y2", width - margin.left - margin.right).attr('stroke-opacity', 0.1); var rect = svg.selectAll("rect") .data(dataset) .enter().append("rect") .attr("x", d => xScale(d.start)) .attr("y", (d, i)=> yScale(i)) .attr("width", d => xScale(d.end)-xScale(d.start)) .attr("height", yScale.bandwidth()) .attr("fill", d => d3.interpolateBlues(d.profit/max_prof)) .on("mouseover", function(d,i){ // Get this bar's x/y values, then augment for the tooltip var xpos = parseFloat(d3.select(this).attr("x")); var ypos = parseFloat(d3.select(this).attr("y"))+ yScale.bandwidth() / 2; // Create the tooltip label as an SVG group `tgrp` with a text and a rect inside var tgrp = svg.append("g") .attr("id", "tooltip") .attr("transform", (d, i) => `translate(${xpos},${ypos})`); tgrp.append("rect") .attr("width", "130px") .attr("height", "22px") .attr("fill", "rgba(255,255,255,0.8)") tgrp.append("text") .attr("x", 5) .attr("y", 14) .attr("text-anchor", "left") .attr("font-family", "sans-serif") .attr("font-size", "11px") .attr("font-weight", "bold") .attr("fill", "black") .text("Start:"+dataset[dataset.indexOf(i)].start+ " End:"+dataset[dataset.indexOf(i)].end+ " Profit:" + dataset[dataset.indexOf(i)].profit); }) .on("mouseout", function(d) { // Remove the tooltip d3.select("#tooltip").remove(); }); svg.node().reset = () =>{ svg.selectAll("rect") .sort((a, b) => d3.ascending(a.id, b.id)) .transition() // optional animation .duration(1000) // optional animation .attr("y", (d, i)=> yScale(i)); } svg.node().sort = () =>{ svg.selectAll("rect") .sort((a, b) => d3.ascending(parseInt(String(a.start)+String(a.end)), parseInt(String(b.start)+String(b.end)))) .transition() // optional animation .duration(1000) // optional animation .attr("y", (d, i)=> yScale(i)) } return svg.node(); }30:T55f,bottom_chart = { const svg = d3.select(DOM.svg(width, height)); const axis = xAxis(svg); const rect = add_sorted_rect(sort_data, "bottom", svg); svg.selectAll("rect") .data(sort_data) .on("mouseover", function(d,i){ // Get this bar's x/y values, then augment for the tooltip var xpos = parseFloat(d3.select(this).attr("x")); var ypos = parseFloat(d3.select(this).attr("y"))+ yScale.bandwidth() / 2; // Create the tooltip label as an SVG group `tgrp` with a text and a rect inside var tgrp = svg.append("g") .attr("id", "tooltip") .attr("transform", (d, i) => `translate(${xpos},${ypos})`); tgrp.append("rect") .attr("width", "130px") .attr("height", "22px") .attr("fill", "rgba(255,255,255,0.8)") tgrp.append("text") .attr("x", 5) .attr("y", 14) .attr("text-anchor", "left") .attr("font-family", "sans-serif") .attr("font-size", "11px") .attr("font-weight", "bold") .attr("fill", "black") .text("Start:"+sort_data[sort_data.indexOf(i)].start+ " End:"+sort_data[sort_data.indexOf(i)].end+ " Profit:" + sort_data[sort_data.indexOf(i)].profit); }) .on("mouseout", function(d) { // Remove the tooltip d3.select("#tooltip").remove(); }); return svg.node(); }31:T559,top_chart = { const svg = d3.select(DOM.svg(width, height)); const axis = xAxis(svg); const rect = add_sorted_rect(sort_data, "top", svg); svg.selectAll("rect") .data(sort_data) .on("mouseover", function(d,i){ // Get this bar's x/y values, then augment for the tooltip var xpos = parseFloat(d3.select(this).attr("x")); var ypos = parseFloat(d3.select(this).attr("y"))+ yScale.bandwidth() / 2; // Create the tooltip label as an SVG group `tgrp` with a text and a rect inside var tgrp = svg.append("g") .attr("id", "tooltip") .attr("transform", (d, i) => `translate(${xpos},${ypos})`); tgrp.append("rect") .attr("width", "130px") .attr("height", "22px") .attr("fill", "rgba(255,255,255,0.8)") tgrp.append("text") .attr("x", 5) .attr("y", 14) .attr("text-anchor", "left") .attr("font-family", "sans-serif") .attr("font-size", "11px") .attr("font-weight", "bold") .attr("fill", "black") .text("Start:"+sort_data[sort_data.indexOf(i)].start+ " End:"+sort_data[sort_data.indexOf(i)].end+ " Profit:" + sort_data[sort_data.indexOf(i)].profit); }) .on("mouseout", function(d) { // Remove the tooltip d3.select("#tooltip").remove(); }); return svg.node(); }32:T4ff,function hold(mode, node) { node.append("rect") .attr("x", xScale(0)) .attr("y", 0) .attr("width", xScale(total_time)-xScale(0)) .attr("height", 10) .attr("fill", "None") .attr("stroke", "rgb(200,200,200)") .attr("stroke-width", 1); node.append("text") .attr("x", xScale(total_time)+15) .attr("y", 8) .attr("font-size", 12) .attr("stroke-width", 1) .text("Current Check"); var wid_val = null; var color = null; var curr_x = null; if (mode == "top"){ if (top_curr>-1 && top_curr < stage_top || top_curr == job_num-1){ wid_val = xScale(sort_data[top_curr].end)-xScale(sort_data[top_curr].start); color = d3.interpolateBlues(sort_data[top_curr].profit/max_prof); curr_x = xScale(sort_data[top_curr].start) } } if (mode == "bottom" && stage_bottom < job_num){ wid_val = xScale(sort_data[job_num-1-stage_bottom].end)-xScale(sort_data[job_num-1-stage_bottom].start); color = d3.interpolateBlues(sort_data[job_num-1-stage_bottom].profit/max_prof); curr_x = xScale(sort_data[job_num-1-stage_bottom].start) } if (curr_x) node.append("rect") .attr("x", curr_x) .attr("y", 0) .attr("width", wid_val) .attr("height", 10) .attr("fill", color); }33:[] 2d:{"id":"e282af25470fefdf","slug":null,"title":"Job Scheduling Problem","thumbnail":"eb2365682f89826df4012934cf8bc5aaf85eb8e0baaaacd6566bf5da2d8823b0","access_level":"public","create_time":"$D2023-04-13T22:12:26.559Z","update_time":"$D2023-04-20T23:58:58.518Z","view_time":null,"first_public_time":"$D2023-04-13T22:12:26.559Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"668dfbe58de33be6","login":"dw3013","name":"Di Wu","avatar_url":"https://avatars-next.observableusercontent.com/465dd77ca9963f9b479bece8f8e7c78a2598864df804d4924eb4bfca009c494e","tier":"starter_2024"},"version":1671,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"79b247c63406f7d3","login":"dw3013","name":"Di Wu","avatar_url":"https://avatars-next.observableusercontent.com/465dd77ca9963f9b479bece8f8e7c78a2598864df804d4924eb4bfca009c494e","tier":null}],"members":[{"type":"individual","id":"79b247c63406f7d3","login":"dw3013","name":"Di Wu","avatar_url":"https://avatars-next.observableusercontent.com/465dd77ca9963f9b479bece8f8e7c78a2598864df804d4924eb4bfca009c494e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"title":"Job Scheduling Problem","cells":[{"id":0,"value":"# Job Scheduling Problem","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":10,"value":"This project is inspired from the original problem LeetCode 1235 Maximum Profit in Job Scheduling: https://leetcode.com/problems/maximum-profit-in-job-scheduling/description/\n\nWe have several jobs, each with a starting times, an ending times and a profit value. A person will receive some amount of profit (may be money) after finishing a job. Every one loves money! So he wants to get as much profit as he can in a limited time period. I've arranged all jobs along the time line so that you can make sense. Here is an example of the jobs he can pick to do:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1239,"value":"Legend(d3.scaleSequential([0, max_prof], d3.interpolateBlues), {\n title: \"Profit\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":16,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":189,"value":"You can hover your mouse on bars to check details. Now let we start the first step to solve the problem. Click on the \"Sort\" button below to sort all jobs by time. That is what people usually do when they have to clarify their minds to have an idea of the time & importance ranking for their jobs!","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":198,"value":"viewof reset_btn = Inputs.Button(\"Reset\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":319,"value":"viewof sort_btn = Inputs.Button(\"Sort\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1550,"value":"Now you've get a beautiful time schedule! You can also click \"Reset\" to see your orginal version.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":288,"value":"Usually, there will be top-down and bottom up solutions for this kind of problems. For our question, we absolutely have these two solutions. Here, I'll show the progress of the two algorithms and their differences in an interactive way. ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":485,"value":"## Bottom-up","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":487,"value":"For the bottom-up solution, we iteratively calculate the most profit during a period of time and then move on to most profit within a longer time period. The way we move from one period to another depends on the expanding time on next job. You can click \"Start or Restart\" to play the animation.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1381,"value":"viewof start_bottom = Inputs.Button(\"Start or Restart\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1373,"value":"### Progress:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1260,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1371,"value":"### Memory:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1277,"value":"fitting_plan_bottom = {\n const svg = d3.select(DOM.svg(width, 10));\n fitting_plan(\"bottom\", svg);\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1273,"value":"hold_bottom = {\n const svg = d3.select(DOM.svg(width, 10));\n hold(\"bottom\", svg);\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1377,"value":"### Cumulative Profit:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1339,"value":"cumu_bottom = {\n var in_data = bottom_chart_data\n \n const svg = d3.select(DOM.svg(width, 200));\n \n const linePath = add_line_path(in_data, svg);\n \n const axis = cumuAxis(svg, \"Iteration\");\n \n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":293,"value":"## Top-down","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":342,"value":"For the top-down solution, back-tracking and recursion are applied to calculate total profit for each branch. Here we mark the bars involved but currently not used in backtracking in a different color. During the process, comparisons between two branches will be done so as to greedily get the max profit.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":1387,"value":"viewof start_top = Inputs.Button(\"Start or Restart\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":500,"value":"### Progress:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":357,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":957,"value":"### Memory:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":815,"value":"fitting_plan_top = {\n const svg = d3.select(DOM.svg(width, 10));\n fitting_plan(\"top\", svg);\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":894,"value":"hold_top = {\n const svg = d3.select(DOM.svg(width, 10));\n hold(\"top\", svg);\n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":502,"value":"### Cumulative Profit:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":579,"value":"cumu_top = {\n var in_data = top_chart_data\n \n const svg = d3.select(DOM.svg(width, 200));\n \n const linePath = add_line_path(in_data, svg);\n \n const axis = cumuAxis(svg, \"Recursion\");\n \n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":493,"value":"## Discussion","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":495,"value":"These two algorithm are supposed to have the same profit changing path due to their common intrinsics in data processing. However, the bottom-up solution is an iterative algorithm while the top-down solution is a recursive algorithm. Thus, we can see time scheduling charts of different colors of rectangles representing the using states. For the bottom up way, it is more straight forward and has few job active for use. For the top-down way, it involves more jobs active for calculation and could considered more possible variables passed by recursion. Both of them are usual and effective ways to solve this kind of problems.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":181,"value":"## Parameters and Functions","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":48,"value":"total_time = 20","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":50,"value":"max_prof = 20","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":52,"value":"job_num = 30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":58,"value":"dataset = {\n const profit = Array.from({length: job_num}, () => Math.floor(Math.random() * (max_prof-1)+1));\n const time1 = Array.from({length: job_num}, () => Math.floor(Math.random() * (total_time-1)));\n const duration = Array.from({length: job_num}, () => Math.floor(Math.random() * total_time * 0.4+1));\n var tuples = [];\n for (let i = 0; i < job_num; i++){\n tuples.push({id:i, start:time1[i], end:(time1[i]+duration[i]> total_time)?total_time:(time1[i]+duration[i]), profit: profit[i]})\n }\n return tuples\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":511,"value":"sort_data = dataset.sort((a, b) => d3.ascending(parseInt(String(a.start)+String(a.end)), parseInt(String(b.start)+String(b.end))))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":204,"value":"reset_listener = {\n reset_btn;\n original_chart.reset();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":323,"value":"sort_listener = {\n sort_btn;\n original_chart.sort();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":111,"value":"width = 1000","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":113,"value":"height = 245","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":118,"value":"margin = ({ top: 20, right: 100, bottom: 20, left: 20 })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":105,"value":"xScale = d3.scaleLinear()\n .domain([0, total_time])\n .range([margin.left, width - margin.right])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":108,"value":"yScale = d3.scaleBand()\n .domain(d3.range(job_num))\n .range([height-margin.bottom, margin.top])\n .padding(0.05)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1157,"value":"cumuXScale = d3.scaleLinear()\n .domain([0, job_num-1])\n .range([margin.left, width - margin.right]);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1159,"value":"cumuYScale = d3.scaleLinear()\n .domain([0, top_down[job_num-1].sum])\n .range([200 - margin.bottom, margin.top]);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":116,"value":"function xAxis(node){\n node.append('g')\n .attr('transform', `translate(0, 20)`)\n .attr(\"class\", \"xAxis\")\n .call(d3.axisTop(xScale));\n\n node.append(\"text\")\n .attr(\"x\", width-80)\n .attr(\"y\", 20)\n .attr(\"font-size\", 12)\n .attr(\"stroke-width\", 1)\n .text(\"Time\");\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1212,"value":"function cumuAxis(node, label) {\n node.append('g')\n .attr('transform', `translate(0, ${200-margin.bottom})`)\n .attr(\"class\", \"xAxis\")\n .call(d3.axisBottom(cumuXScale));\n \n node.append(\"text\")\n .attr(\"x\", width-90)\n .attr(\"y\", 195)\n .attr(\"font-size\", 12)\n .attr(\"stroke-width\", 1)\n .text(label);\n\n node.append('g')\n .attr('transform', `translate(${margin.left}, 0)`)\n .attr(\"class\", \"yAxis\")\n .call(d3.axisLeft(cumuYScale));\n \n node.append(\"text\")\n .attr(\"x\", 0)\n .attr(\"y\", 10)\n .attr(\"font-size\", 12)\n .attr(\"stroke-width\", 1)\n .text(\"Cumulative Profit\");\n }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1193,"value":"function add_sorted_rect(sort_data, mode, node){\n var rect = node.selectAll(\"rect\")\n .data(sort_data)\n .enter().append(\"rect\")\n .attr(\"x\", d => xScale(d.start))\n .attr(\"y\", (d, i)=> yScale(i))\n .attr(\"width\", d => xScale(d.end)-xScale(d.start))\n .attr(\"height\", yScale.bandwidth())\n .attr(\"fill\", function(d, i){\n if (mode == \"top\"){\n if (i == top_curr) return \"yellow\";\n else if (i > top_curr) return d3.interpolateBlues(d.profit/max_prof);\n else return d3.interpolateOranges(d.profit/max_prof);\n }\n if (mode == \"bottom\"){\n // if (i > job_num-1-stage_bottom) return d3.interpolateOranges(d.profit/max_prof);\n // else\n if (i == job_num-1-stage_bottom) return \"yellow\";\n else return d3.interpolateBlues(d.profit/max_prof);\n }\n })\n \n return rect;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1178,"value":"function add_line_path(in_data, node){\n var data = []\n\n for(let i=0; i cumuXScale(i))\n .attr(\"cy\", (d, i) => cumuYScale(d.sum))\n .attr(\"r\", 5)\n .attr(\"fill\",\"white\");\n\n node.selectAll(\"text\")\n .data(in_data)\n .enter()\n .append(\"text\")\n .attr(\"x\", (d, i) => cumuXScale(i)-5)\n .attr(\"y\", (d, i) => cumuYScale(d.sum))\n .attr(\"font-size\", 10)\n .attr(\"stroke-width\", 1)\n .text(function(d) {\n return d.sum\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1280,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1295,"value":"function fitting_plan(mode, node) {\n node.append(\"rect\")\n .attr(\"x\", xScale(0))\n .attr(\"y\", 0)\n .attr(\"width\", xScale(total_time)-xScale(0))\n .attr(\"height\", 10)\n .attr(\"fill\", \"None\")\n .attr(\"stroke\", \"rgb(200,200,200)\")\n .attr(\"stroke-width\", 1);\n\n node.append(\"text\")\n .attr(\"x\",xScale(total_time)+20)\n .attr(\"y\", 8)\n .attr(\"font-size\", 12)\n .attr(\"stroke-width\", 1)\n .text(\"Held Best\");\n\n if (mode == \"top\")\n var data = top_chart_data;\n if (mode == \"bottom\")\n var data = bottom_chart_data;\n\n const ele_len = data.length;\n if (ele_len){\n var eles = data[data.length-1].elements;\n for (let i=0; i 1)\n mutable stage_bottom = 0;\n if(start_bottom == 1)\n return 1;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1077,"value":"mutable stage_bottom = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1137,"value":"bottom_reset = {\n if (stage_bottom > job_num-1)\n mutable stage_bottom = 0;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1130,"value":"timer_bottom = {\n let interval = null;\n if(bottom_start_listener){\n clearInterval(interval);\n interval = setInterval(function () {\n mutable stage_bottom += 1; \n }, 500);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7,"value":"bottom_up = {\n const dp = Array(sort_data.length).fill({});\n \n function binarySearch(idx) {\n let low = idx+1, high = sort_data.length;\n\n while(low < high) {\n const mid = Math.floor((low + high)/2);\n\n if(sort_data[mid].start >= sort_data[idx].end) high = mid;\n else low = mid + 1;\n }\n return low;\n }\n \n dp[sort_data.length-1] = {id:0, sum:sort_data[sort_data.length-1].profit, elements:[sort_data.length-1]};\n var iter = 1;\n \n for(let i = sort_data.length-2; i >= 0; i--) {\n const next = binarySearch(i)\n var tmp = {sum:0, elements:[]}\n if (next < sort_data.length)\n tmp = dp[next]\n if (dp[i+1].sum >= sort_data[i].profit + tmp.sum)\n dp[i] = {id:iter, sum: dp[i+1].sum, elements:dp[i+1].elements};\n else\n dp[i] = {id:iter, sum: sort_data[i].profit + tmp.sum, elements:[i].concat(tmp.elements)};\n iter += 1\n }\n \n return dp.reverse();\n};","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1113,"value":"bottom_chart_data = {\n return bottom_up.slice(0, stage_bottom+1);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":939,"value":"mutable stage_top = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":550,"value":"mutable top_curr = {\n if (stage_top < job_num)\n return stage_top;\n else\n return job_num*2-2-stage_top;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":413,"value":"top_reset = {\n if (stage_top > 2*job_num-2)\n mutable stage_top = 0;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1509,"value":"top_start_listener = {\n if (start_top > 1)\n mutable stage_top = 0;\n if(start_top == 1)\n return 1;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1002,"value":"timer_top = {\n let interval = null;\n if(top_start_listener){\n clearInterval(interval);\n interval = setInterval(function () {\n mutable stage_top += 1; \n }, 500);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":587,"value":"top_down = {\n var memo = {};\n var hold = [];\n var i = 0;\n function run(idx) {\n if(idx >= job_num) return {sum:0, elements:[]};\n if(memo[idx]) return memo[idx];\n \n let next = idx+1;\n while(next < job_num && sort_data[next].start < sort_data[idx].end) next++;\n const one = run(idx+1);\n const two = run(next);\n // console.log(idx+1, next);\n if(one.sum > two.sum+sort_data[idx].profit){ memo[idx] = one;}\n else memo[idx] = {sum:two.sum+sort_data[idx].profit, elements:[idx].concat(two.elements)}\n\n hold.push({id:i, sum:memo[idx].sum, elements:memo[idx].elements});\n i += 1;\n return memo[idx];\n }\n run(0);\n return hold;\n};","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":787,"value":"top_chart_data = {\n if (stage_top > top_curr || stage_top == job_num-1){\n var tmp = (stage_top-top_curr)/2+1;\n return top_down.slice(0, tmp);\n }\n \n return []\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":581,"value":"import {InlineChart} from \"@d3/inline-labels\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":200,"value":"Inputs = require(\"@observablehq/inputs@0.7.8/dist/inputs.umd.min.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":1250,"value":"import {Legend, Swatches} from \"@d3/color-legend\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 2e:"$2d:body"