import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
class Line implements Comparable<Line> {
int start;
int end;
public Line(int start, int end) {
super();
this.start = start;
this.end = end;
}
/**
* Line l |----------------------------|
* |----|
* |----------------|
* |-------------------------------------------|
* |-------------------|
* |--------------------------------|
* |------------|
*/
@Override
public int compareTo(Line line) {
if (start < line.start) {
return -1;
} else if (end > line.end) { // start >= l.start
return 1;
} else if (start == line.start && end == line.end) {
return 0;
} else if (start == line.start && end < line.end) {
return -1;
} else {// (start > l.start && end <= l.end)
return 1;
}
}
public boolean isMergeable(Line line) {
if (end < line.start || start > line.end)
return false;
return true;
}
public Line merge(Line line) {
int x = (line.start <= start) ? line.start : start;
int y = (line.end >= end) ? line.end : end;
return new Line(x, y);
}
@Override
public String toString() {
return "[" + start + "," + end + "]";
}
}
public class MergeAndSort {
/**
* @param args
*/
public static void main(String[] args) {
mergeAndSort(new Line[] { new Line(1, 2), new Line(1, 5),
new Line(2, 8), new Line(4, 7), new Line(3, 9), new Line(4, 5),
new Line(6, 7), new Line(5, 10) });
mergeAndSort(new Line[] { new Line(1, 2), new Line(3, 5),
new Line(7, 8), new Line(4, 7) });
mergeAndSort(new Line[] { new Line(3, 5), new Line(1, 8),
new Line(8, 8 ) });
}
private static void mergeAndSort(Line[] lineArray) {
List<Line> lineList = new ArrayList<Line>();
lineList.addAll(Arrays.asList(lineArray));
System.out.print("Origin:");
printLines(lineList);
Collections.sort(lineList);
System.out.print("Sorted:");
printLines(lineList);
List<Line> mergedList = merge(lineList);
System.out.print("Merged:");
printLines(mergedList);
System.out.println();
}
private static List<Line> merge(List<Line> lineList) {
List<Line> mergedList = new ArrayList<Line>();
Iterator<Line> itr = lineList.iterator();
if (itr.hasNext()) {
Line current = itr.next();
while (itr.hasNext()) {
Line next = itr.next();
if (current.isMergeable(next)) {
current = current.merge(next);
} else {
System.out.println("[DEBUG] current " + current
+ " can't merge next " + next);
mergedList.add(current);
current = next;
}
}
mergedList.add(current);
}
return mergedList;
}
private static void printLines(List<Line> lineList) {
for (Line line : lineList) {
System.out.print(line);
System.out.print(" ");
}
System.out.println();
}
}