Skip to content

Commit 5affb4d

Browse files
author
Christian Bender
authored
Merge pull request TheAlgorithms#309 from YooSeonjae/master
Scheduling to Minimize Lateness ( Greedy Algorithm )
2 parents 2029156 + 6c0c2f0 commit 5affb4d

File tree

4 files changed

+282
-0
lines changed

4 files changed

+282
-0
lines changed

‎ClosestPair/ClosestPair.java

Lines changed: 211 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,211 @@
1+
import java.io.*;
2+
import java.util.*;
3+
4+
public class ClosestPair {
5+
static int count = 0;// array length
6+
static int secondCount = 0;// array length
7+
static Location array[] = new Location[10000];
8+
static Location point1 = null; // Minimum point coordinate
9+
static Location point2 = null; // Minimum point coordinate
10+
static double minNum = Double.MAX_VALUE;// Minimum point length
11+
12+
private static class Location { // Location class
13+
double x = 0, y = 0;
14+
15+
public Location(double x, double y) { //Save x, y coordinates
16+
this.x = x;
17+
this.y = y;
18+
}
19+
}
20+
21+
public static int xPartition(Location[] a, int first, int last) { // x-axis Quick Sorting
22+
Location pivot = a[last]; // pivot
23+
int pIndex = last;
24+
int i = first - 1;
25+
Location temp; // Temporarily store the value for position transformation
26+
for (int j = first; j <= last - 1; j++) {
27+
if (a[j].x <= pivot.x) { // Less than or less than pivot
28+
i++;
29+
temp = a[i]; // array[i] <-> array[j]
30+
a[i] = a[j];
31+
a[j] = temp;
32+
}
33+
}
34+
i++;
35+
temp = a[i];// array[pivot] <-> array[i]
36+
a[i] = a[pIndex];
37+
a[pIndex] = temp;
38+
return i;// pivot index
39+
}
40+
public static int yPartition(Location[] a, int first, int last) { //y-axis Quick Sorting
41+
Location pivot = a[last]; // pivot
42+
int pIndex = last;
43+
int i = first - 1;
44+
Location temp; // Temporarily store the value for position transformation
45+
for (int j = first; j <= last - 1; j++) {
46+
if (a[j].y <= pivot.y) { // Less than or less than pivot
47+
i++;
48+
temp = a[i]; // array[i] <-> array[j]
49+
a[i] = a[j];
50+
a[j] = temp;
51+
}
52+
}
53+
i++;
54+
temp = a[i];// array[pivot] <-> array[i]
55+
a[i] = a[pIndex];
56+
a[pIndex] = temp;
57+
return i;// pivot index
58+
}
59+
60+
public static void xQuickSort(Location[] a, int first, int last) { //x-axis Quick Sorting
61+
if (first < last) {
62+
int q = xPartition(a, first, last); // pivot
63+
xQuickSort(a, first, q - 1); // Left
64+
xQuickSort(a, q + 1, last); // Right
65+
}
66+
}
67+
68+
public static void yQuickSort(Location[] a, int first, int last) { //y-axis Quick Sorting
69+
if (first < last) {
70+
int q = yPartition(a, first, last); // pivot
71+
yQuickSort(a, first, q - 1); // Left
72+
yQuickSort(a, q + 1, last); // Right
73+
}
74+
}
75+
76+
public static double closestPair(Location[] a, int indexNum, int first, int last) {// closestPair
77+
Location divideArray[] = new Location[indexNum]; // array stored before divide
78+
System.arraycopy(a, 0, divideArray, 0, indexNum); // Copy from previous array
79+
80+
int totalNum = indexNum; // number of coordinates in the divideArray array
81+
int divideX = indexNum / 2; // Intermediate value for divide
82+
Location leftArray[] = new Location[divideX]; //divide - left array
83+
Location rightArray[] = new Location[totalNum - divideX]; //divide - right array
84+
85+
if (indexNum <= 3) { // If the number of coordinates is 3 or less
86+
return bruteForce(divideArray);
87+
}
88+
System.arraycopy(divideArray, 0, leftArray, 0, divideX); //divide - left array
89+
System.arraycopy(divideArray, divideX, rightArray, 0, totalNum - divideX); //divide - right array
90+
91+
double minLeftArea = 0; //Minimum length of left array
92+
double minRightArea = 0; //Minimum length of right array
93+
double minValue = 0; //Minimum lengt
94+
95+
minLeftArea = closestPair(leftArray, divideX, 0, divideX - 1); // recursive closestPair
96+
minRightArea = closestPair(rightArray, totalNum - divideX, divideX, totalNum - divideX - 1);
97+
minValue = Math.min(minLeftArea, minRightArea);// window size (= minimum length)
98+
99+
// Create window
100+
for (int i = 0; i < totalNum; i++) { // Set the size for creating a window and creating a new array for the coordinates in the window
101+
double xGap = Math.abs(divideArray[divideX].x - divideArray[i].x);
102+
if (xGap < minValue) {
103+
secondCount++; // size of the array
104+
} else {
105+
if (divideArray[i].x > divideArray[divideX].x) {
106+
break;
107+
}
108+
}
109+
}
110+
Location firstWindow[] = new Location[secondCount]; // new array for coordinates in window
111+
int k = 0;
112+
for (int i = 0; i < totalNum; i++) {
113+
double xGap = Math.abs(divideArray[divideX].x - divideArray[i].x);
114+
if (xGap < minValue) { // if it's inside a window
115+
firstWindow[k] = divideArray[i]; // put in an array
116+
k++;
117+
} else {
118+
if (divideArray[i].x > divideArray[divideX].x) {
119+
break;
120+
}
121+
}
122+
}
123+
yQuickSort(firstWindow, 0, secondCount - 1);// Sort by y coordinates
124+
/ * Coordinates in Window * /
125+
double length = 0;
126+
for (int i = 0; i < secondCount - 1; i++) { // size comparison within window
127+
for (int j = (i + 1); j < secondCount; j++) {
128+
double xGap = Math.abs(firstWindow[i].x - firstWindow[j].x);
129+
double yGap = Math.abs(firstWindow[i].y - firstWindow[j].y);
130+
if (yGap < minValue) {
131+
length = (double) Math.sqrt(Math.pow(xGap, 2) + Math.pow(yGap, 2));
132+
if (length < minValue) { // If the measured distance is less than the current minimum distance
133+
minValue = length;// Change minimum distance to current distance
134+
if (length < minNum) { // Conditional statement for registering final coordinate
135+
minNum = length;
136+
point1 = firstWindow[i];
137+
point2 = firstWindow[j];
138+
}
139+
}
140+
}
141+
else
142+
break;
143+
}
144+
}
145+
secondCount = 0;
146+
return minValue;
147+
}
148+
149+
public static double bruteForce(Location[] array) { // When the number of coordinates is less than 3
150+
double minValue = Double.MAX_VALUE; // minimum distance
151+
double length = 0;
152+
double xGap = 0, yGap = 0; // Difference between x, y coordinates
153+
if (array.length == 2) { // When there are two coordinates
154+
xGap = (array[0].x - array[1].x); // Difference between x coordinates
155+
yGap = (array[0].y - array[1].y); // Difference between y coordinates
156+
length = (double) Math.sqrt(Math.pow(xGap, 2) + Math.pow(yGap, 2)); // distance between coordinates
157+
if (length < minNum) { // Conditional statement for registering final coordinate
158+
minNum = length;
159+
point1 = array[0];
160+
point2 = array[1];
161+
}
162+
return length;
163+
} else if (array.length == 3) { // When there are 3 coordinates
164+
for (int i = 0; i < array.length - 1; i++) {
165+
for (int j = (i + 1); j < array.length; j++) {
166+
xGap = (array[i].x - array[j].x); // Difference between x coordinates
167+
yGap = (array[i].y - array[j].y); // Difference between y coordinates
168+
length = (double) Math.sqrt(Math.pow(xGap, 2) + Math.pow(yGap, 2)); // distance between coordinates
169+
if (length < minValue) { // If the measured distance is less than the current minimum distance
170+
minValue = length; // Change minimum distance to current distance
171+
if (length < minNum) { // Conditional statement for registering final coordinate
172+
minNum = length;
173+
point1 = array[i];
174+
point2 = array[j];
175+
}
176+
}
177+
}
178+
}
179+
return minValue;
180+
}
181+
return minValue;
182+
}
183+
184+
public static void main(String[] args) throws IOException {
185+
// TODO Auto-generated method stub
186+
StringTokenizer token;
187+
188+
BufferedReader in = new BufferedReader(new FileReader("closest_data.txt"));
189+
//Input data consists of one x-coordinate and one y-coordinate
190+
String ch;
191+
192+
System.out.println("Input data");
193+
while ((ch = in.readLine()) != null) {
194+
token = new StringTokenizer(ch, " ");
195+
196+
array[count] = new Location(Double.parseDouble(token.nextToken()), Double.parseDouble(token.nextToken())); // put in an array
197+
count++; // the number of coordinates actually in the array
198+
System.out.println("x: "+array[count - 1].x + ", y: " + array[count - 1].y);
199+
}
200+
201+
xQuickSort(array, 0, count - 1); // Sorting by x value
202+
203+
double result; // minimum distance
204+
result = closestPair(array, count, 0, count - 1); // ClosestPair start
205+
System.out.println("Output Data");// minimum distance coordinates and distance output
206+
System.out.println("(" + point1.x + ", " + point1.y + ")");
207+
System.out.println("(" + point2.x + ", " + point2.y + ")");
208+
System.out.println("Minimum Distance : " + result);
209+
210+
}
211+
}

‎ClosestPair/closest_data.txt

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
2 3
2+
2 16
3+
3 9
4+
6 3
5+
7 7
6+
9 12
7+
10 11
8+
15 2
9+
15 19
10+
16 11
11+
17 13
12+
19 4

‎MinimizingLateness/MinimizingLateness.java

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
import java.io.*;
2+
import java.util.*;
3+
4+
public class MinimizingLateness {
5+
6+
private static class Schedule { // Schedule class
7+
int t = 0; // Time required for the operation to be performed
8+
int d = 0; // Time the job should be completed
9+
int s = 0; // Start time of the task
10+
int f = 0; // End time of the operation
11+
12+
public Schedule(int t, int d) {
13+
this.t = t;
14+
this.d = d;
15+
}
16+
}
17+
18+
public static void main(String[] args) throws IOException {
19+
// TODO Auto-generated method stub
20+
StringTokenizer token;
21+
22+
String ch;
23+
BufferedReader in = new BufferedReader(new FileReader("input.txt"));
24+
int indexCount; // size of array index
25+
ch = in.readLine();
26+
indexCount = Integer.parseInt(ch); // The first line specifies the size of the operation (= the size of the array)
27+
System.out.println("Input Data : ");
28+
System.out.println(indexCount); // number of operations
29+
Schedule array[] = new Schedule[indexCount]; // Create an array to hold the operation
30+
int i = 0;
31+
while ((ch = in.readLine()) != null) {
32+
token = new StringTokenizer(ch, " ");
33+
// Include the time required for the operation to be performed in the array and the time it should be completed.
34+
array[i] = new Schedule(Integer.parseInt(token.nextToken()), Integer.parseInt(token.nextToken()));
35+
i++; // 다음 인덱스
36+
System.out.println(array[i - 1].t + " " + array[i - 1].d);
37+
}
38+
39+
int tryTime = 0; // Total time worked
40+
int lateness = 0; // Lateness
41+
for (int j = 0; j < indexCount - 1; j++) {
42+
array[j].s = tryTime; // Start time of the task
43+
array[j].f = tryTime + array[j].t; // Time finished
44+
tryTime = tryTime + array[j].t; // Add total work time
45+
// Lateness
46+
lateness = lateness + Math.max(0, tryTime - array[j].d);
47+
}
48+
System.out.println();
49+
System.out.println("Output Data : ");
50+
System.out.println(lateness);
51+
}
52+
}

‎MinimizingLateness/data06_lateness.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
6
2+
3 6
3+
2 8
4+
1 9
5+
4 9
6+
3 14
7+
2 15

0 commit comments

Comments
 (0)