Weighted-Interval-Scheduling-Using-Bottom-Up-Dynamic-Programming/WISmain.cpp at master · danieldotwav/Weighted-Interval-Scheduling-Using-Bottom-Up-Dynamic-Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
// Program Summary: This program implements the Weighted Interval Scheduling algorithm using a bottom-up dynamic programming approach. The program is designed to find the optimal set of non-overlapping jobs (intervals) that maximizes the total profit, where each job has a start time, finish time, and profit (weight).

#include "WISheader.h"; // Contains WIS class definition/implementation
#include "WISalgorithm.h"; // Contains implementation of the main algorithm and utility functions
using namespace std;


int main() {
	cout << "++++ Weighted Interval Sceduling with Bottom up dynamic programming ++++\n";

	// Get number of intervals to process from user
	int intervals = promptUserForNumIntervals();

	// Create and populate container to store jobs
	vector<WIS> jobs = generateWISVectorFromUserInput(intervals);

	// Display the results
	cout << "\nSorted Input Intervals By Finishing Time:\n";
	printFormattedInputIntervals(jobs);

	/* MAIN ALGORITHM */
	vector<WIS> optimalSet = getOptimalSet(jobs);

	// Display the schedules that comprise the maximum profit
	cout << "\nThe jobs involved in the maximum profit are: ";
	printOptimalSet(optimalSet);

	cout << "\n\nTerminating program...\n";
	return 0;
}

/* === Test Cases ===

Case 1:
6 Intervals
1 3 5
2 5 6
4 6 5
6 7 4
5 8 11
7 9 2

Expected Optimal Job Set: {(2, 5, 6) (5, 8, 11)}
Expected Maximum Profit: 17


Case 2:
4 Intervals
1 2 50
3 5 20
6 19 100
2 10 200

Expected Optimal Job Set: {(1, 2, 50) (2, 10, 200)}
Expected Maximum Profit: 250


Case 3:
7 Intervals
1 4 3
3 5 2
0 6 9
4 7 7
3 8 4
5 9 4
6 10 10

Expected Optimal Job Set: {(1, 4, 3) (6, 10, 10)}
Expected Maximum Profit: 13


Case 4:
8 Intervals
6 8 2
5 7 1
8 11 4
3 5 1
4 7 1
0 3 5
1 4 2
7 9 3

Expected Optimal Job Set: {(1, 4, 2) (6, 8, 2) (8, 11, 4)}
Expected Maximum Profit: 8


Case 5:
6 Intervals
5 7 7
7 8 2
8 9 1
9 11 2
11 12 3
4 8 2

Expected Optimal Job Set: {(5, 7, 7) (7, 8, 2) (8, 9, 1) (9, 11, 2) (11, 12, 3)}
Expected Maximum Profit: 15


Case 6:
7 Intervals
4 7 4
7 4 2
x 9 1
9 11 2
1 3 3
8 1 9
2 4 6

Expected Optimal Job Set: {(2, 4, 6) (4, 7, 4) (9, 11, 2)}
Expected Maximum Profit: 12


Case 7:
1 Intervals
0 0 0

Expected Optimal Job Set: {}
Expected Maximum Profit: 0


Case 8:
3 Intervals
1 2 3
1 2 3
1 2 3

Expected Optimal Job Set: {(1, 2, 3)}
Expected Maximum Profit: 3

Case 9:
3 Intervals
1 2 4
1 2 8
1 2 4


Case 10:
5 Intervals

4 7 9
0 4 7
1 4 6
6 6 4
7 10 5

*/