File tree Expand file tree Collapse file tree
etc/job_scheduling/job_scheduling Expand file tree Collapse file tree Original file line number Diff line number Diff line change 4141 "merge" : " Merge Sort"
4242 "radix" : " Radix Sort"
4343 "quick" : " Quicksort"
44- "heap" : " Heapsort"
44+ "heap" : " Heapsort"
4545 "shell" : " Shellsort"
4646 "cycle" : " Cycle Sort"
4747 "comb" : " Comb Sort"
4848 }
4949 },
5050 "string" : {
51- "name" : " String"
52- "list" : {
53- "edit_distance" : " Edit Distance"
54- "knuth_morris_pratt" : " KMP Substring Search"
55- "rabin_karp_algorithm" : " Rabin-Karp Algorithm"
56- }
57- },
58- "dp" : {
51+ "name" : " String"
52+ "list" : {
53+ "edit_distance" : " Edit Distance"
54+ "knuth_morris_pratt" : " KMP Substring Search"
55+ "rabin_karp_algorithm" : " Rabin-Karp Algorithm"
56+ }
57+ },
58+ "dp" : {
5959 "name" : " Dynamic Programming"
6060 "list" : {
6161 "fibonacci" : " Fibonacci Sequence"
6767 "integer_partition" : " Integer Partition"
6868 "ugly_numbers" : " Ugly Numbers"
6969 }
70- },
70+ },
71+ "greedy" : {
72+ "name" : " Greedy"
73+ "list" : {
74+ "job_scheduling" : " Job Scheduling Problem"
75+ }
76+ },
7177 "etc" : {
7278 "name" : " Uncategorized"
7379 "list" : {
74- "flood_fill" : " Flood Fill"
75- "job_scheduling" : " Job Scheduling Problem"
80+ "flood_fill" : " Flood Fill"
7681 }
7782 }
7883}
Load diff This file was deleted.
File renamed without changes.
Original file line number Diff line number Diff line change 1+ // sort according to decreasing order of profit
2+ // Bubble sort implemented ... Implement a better algorithm for better performance
3+ for ( var i = 0 ; i < N - 1 ; i ++ ) {
4+ for ( var j = 0 ; j < N - i - 1 ; j ++ ) {
5+ if ( profit [ j ] < profit [ j + 1 ] ) {
6+ var temp = profit [ j ] ;
7+ profit [ j ] = profit [ j + 1 ] ;
8+ profit [ j + 1 ] = temp ;
9+ temp = deadline [ j ] ;
10+ deadline [ j ] = deadline [ j + 1 ] ;
11+ deadline [ j + 1 ] = temp ;
12+ var t = jobId [ j ] ;
13+ jobId [ j ] = jobId [ j + 1 ] ;
14+ jobId [ j + 1 ] = t ;
15+ }
16+ }
17+ }
18+
19+ var slot = new Array ( N ) ;
20+ var result = new Array ( N ) ;
21+ for ( var i = N - 1 ; i >= 0 ; i -- ) {
22+ result [ i ] = '-' ;
23+ }
24+ tracer . _setData ( jobId ) ;
25+ tracer1 . _setData ( deadline ) ;
26+ tracer2 . _setData ( profit ) ;
27+ tracer3 . _setData ( result ) ;
28+
29+ // Initialise all slots to free
30+ for ( var i = 0 ; i < N ; i ++ ) {
31+ slot [ i ] = 0 ;
32+ }
33+
34+ // Iterate through all the given jobs
35+ for ( var i = 0 ; i < N ; i ++ ) {
36+ /*
37+ Start from the last possible slot.
38+ Find a slot for the job
39+ */
40+ tracer . _select ( i ) . _wait ( ) ;
41+ tracer1 . _select ( i ) . _wait ( ) ;
42+ for ( var j = Math . min ( N , deadline [ i ] ) - 1 ; j >= 0 ; j -- ) {
43+ if ( slot [ j ] === 0 ) {
44+ tracer3 . _notify ( j , jobId [ i ] ) . _wait ( ) ;
45+ result [ j ] = jobId [ i ] ;
46+ slot [ j ] = 1 ;
47+ tracer3 . _denotify ( j ) ;
48+ break ;
49+ }
50+ }
51+ tracer . _deselect ( i ) ;
52+ tracer1 . _deselect ( i ) ;
53+ }
54+
File renamed without changes.
You can’t perform that action at this time.
0 commit comments