29:null 2a:["$","title",null,{"children":"Job Scheduling Problem | Di Wu | Observable"}] 2f:T89a,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 => colorScale(d.profit)) .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().sort = () =>{ svg.selectAll("rect") .sort((a, b) => d3.ascending(String(a.start)+String(a.end), String(b.start)+String(b.end))) .transition() // optional animation .duration(1000) // optional animation .attr("y", (d, i)=> yScale(i)) } 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)); } return svg.node(); }30:T70a,top_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(sort_data) .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", function(d, i){ if (i > top_curr) return colorScale(d.profit); else return d3.interpolateOranges(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:"+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:T53e,cum_top = { var data = [] var in_data = top_chart_data const n_height = 200 const x_scale = d3.scaleLinear() .domain([0, job_num-1]) .range([margin.left, width - margin.right]); const y_scale = d3.scaleLinear() .domain([0, top_down[job_num-1].sum]) .range([n_height - margin.bottom, margin.top]); const svg = d3.select(DOM.svg(width, n_height)); function iter_axis(g) { g.attr('transform', `translate(0, 180)`) .attr("class", "xAxis") .call(d3.axisBottom(x_scale)) } for(let i=0; i x_scale(i)) .attr("cy", (d, i) => y_scale(d.sum)) .attr("r", 5) .attr("fill","white"); svg.selectAll("text") .data(in_data) .enter() .append("text") .attr("x", (d, i) => x_scale(i)-5) .attr("y", (d, i) => y_scale(d.sum)) .attr("font-size", 10) .attr("stroke-width", 1) .text(function(d) { return d.sum }); var axis = svg.append('g') .call(iter_axis); return svg.node(); }32:[] 2d:{"id":"24e134d236590d2b","slug":null,"title":"Job Scheduling Problem","thumbnail":"3be7a3bb4197f962ec443947a3b04fd5c0f2893568aa905922cf6b42dfe3dfe1","access_level":"public","create_time":"$D2023-04-18T05:06:21.410Z","update_time":"$D2023-04-18T08:56:28.391Z","view_time":null,"first_public_time":"$D2023-04-18T05:06:21.410Z","fork":{"id":"e282af25470fefdf","slug":null,"title":"Job Scheduling Problem","owner":{"id":"668dfbe58de33be6","login":"dw3013","name":"Di Wu"}},"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":1003,"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":0,"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. Here is an example of the jobs he can pick to do:","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":16,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":189,"value":"We've arrange all jobs on a time line. Now let we start the first step to solve the problem. Click on the sort button above to sort all jobs by starting time.","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 the two solutions. Here, I'll show the progress of the two algorithms and their differences in an interactive way. Two line charts will be plot so as to compare the algos in a quantitive way.","pinned":false,"hidden":false,"mode":"md","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 is applied to calculate total profit for each branch. During the process, comparisons between current branches will be done so as to greedily get the max profit.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":475,"value":"This part is not completed. I plan to complete the part by representing the considering backtrace steps by marking involved bars in a different color. Then a line chart will be applied to trace the change of calculated sum in each stage. In this way, people can have an idea how this algorithm climbs by recursions. Users can look at each stage by pressing the button \"next\".","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined"},{"id":500,"value":"### Progress:","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined"},{"id":410,"value":"viewof top_reset = Inputs.Button(\"Reset\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":361,"value":"viewof top_btn = Inputs.Button(\"Next\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":357,"value":"$30","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 = {\n const svg = d3.select(DOM.svg(width, 20));\n const edge_data = [0,0];\n svg.append(\"rect\")\n .attr(\"x\", xScale(0))\n .attr(\"y\", 0)\n .attr(\"width\", xScale(total_time)-xScale(0))\n .attr(\"height\", 20)\n .attr(\"fill\", \"None\")\n .attr(\"stroke\", \"rgb(200,200,200)\")\n .attr(\"stroke-width\", 1);\n\n const ele_len = top_chart_data.length;\n if (ele_len){\n var eles = top_chart_data[top_chart_data.length-1].elements;\n for (let i=0; i-1 && top_curr < stage || top_curr == job_num-1)\n svg.append(\"rect\")\n .attr(\"x\", xScale(sort_data[top_curr].start))\n .attr(\"y\", 0)\n .attr(\"width\", xScale(sort_data[top_curr].end)-xScale(sort_data[top_curr].start))\n .attr(\"height\", 20)\n .attr(\"fill\", d3.interpolateBlues(sort_data[top_curr].profit/max_prof));\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":"$31","pinned":true,"hidden":false,"mode":"ojs","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 don't need to go back. We greedily get maximum profit we can get from beginning to ending. I plan to use the similar way as top-down to show the progress of algorithm and plot a line chart to learn how the algorithm climbs.","pinned":false,"hidden":false,"mode":"md","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 similarity between the line chart due to their common intrinsics. Some kinds of symmetrical characteristics are supposed to be discovered between the development of calculation for the two methods.","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 = 10","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 = 10","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(String(a.start)+String(a.end), 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":939,"value":"mutable stage = 0","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":413,"value":"top_reset_listener = {\n top_reset;\n mutable stage = 0;\n // mutable top_curr = 0;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":445,"value":"top_listener = {\n // var state = top_btn;\n top_btn;\n mutable stage += 1;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":805,"value":"reminder_top_reset = {\n if (stage > job_num*2-1)\n mutable stage -=1\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":550,"value":"mutable top_curr = {\n if (stage < job_num)\n return stage;\n else\n return job_num*2-2-stage;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":45,"value":"function colorScale(input) {\n return d3.interpolateBlues(input/max_prof) \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":111,"value":"width = 800","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: 20, bottom: 20, left: 50 })","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":116,"value":"xAxis = g => g.attr('transform', `translate(0, 20)`)\n .attr(\"class\", \"xAxis\")\n .call(d3.axisTop(xScale))","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_curr || stage == job_num-1){\n var tmp = (stage-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":7,"value":"bottom_up = function(startTime, endTime, profit) {\n const jobs = [];\n const dp = Array(startTime.length+1).fill(0);\n \n for(let i = 0; i < startTime.length; i++) {\n jobs[i] = [startTime[i], endTime[i], profit[i]];\n }\n jobs.sort((a, b) => a[0] - b[0]);\n \n function binarySearch(idx) {\n let low = idx+1, high = jobs.length;\n \n while(low < high) {\n const mid = Math.floor((low + high)/2);\n \n if(jobs[mid][0] >= jobs[idx][1]) high = mid;\n else low = mid + 1;\n }\n return low;\n }\n \n for(let i = jobs.length-1; i >= 0; i--) {\n const next = binarySearch(i)\n dp[i] = Math.max(dp[i+1], jobs[i][2] + dp[next])\n }\n return dp[0];\n};","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":581,"value":"import {InlineChart} from \"@d3/inline-labels\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":200,"value":"Inputs = require(\"@observablehq/inputs@0.7.8/dist/inputs.umd.min.js\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}} 2e:"$2d:body"