merge range

http://1point3acres.com/bbs/thread-15148-1-1.html

 

一个range的序列,如[1,3], [2,6], [8,10],[15,18]
: 写程序合并有重叠的range,比如上面的序列合并为[1,6], [8,10], [15,18]

我觉得可以只对起点排序。
然后依次扫描。设当前合并段的起点为s, 终点为e。下一个要比较的段,起点为i,终点j:
if(i <= e){
if(j > e) e = j; //合并下一段,延长终点。
}else{
//保存当前s,e,然后开始一个新的合并段
i = s; e = j;
}

void PrintMerge2(int a[], int n)
{
assert(a && n > 0 && n%2 == 0);

int nBeg = a[0];
int nEnd = a[1];

for (int i = 2; i < n; i += 2)
{
if (a[i] > nEnd)
{
cout<<nBeg<<” “<<nEnd<<endl;
nBeg = a[i];
nEnd = a[i+1];
}
else
{
if (a[i+1] > nEnd)
nEnd = a[i+1];
}
}

cout<<nBeg<<” “<<nEnd<<endl;
}

 

 

 

class DataSet {
public int begin;
public int end;

public DataSet(int i, int j) {
begin = i;
end = j;
}
}

class StackX {
private int top;
private int[] stackArray;
private int size;

public StackX(int i) {
top = -1;
size = i;
stackArray = new int[size];
}

public void push(int i) {
stackArray[++top] = i;
}

public int peek() {
return stackArray[top];
}

public int pop() {
int temp = stackArray[top–];
return temp;
}
public boolean isEmpty() {
return top == -1;
}
}

class DSArray {
private DataSet[] DSArr;
private int num;
private final int MAX_NUM = 10;
private int[] elementArr;
private StackX stackImpl;
private DataSet[] newDS;
private int k = 0;

public DSArray() {
DSArr = new DataSet[MAX_NUM];
elementArr = new int[MAX_NUM * 2];
num = 0;
stackImpl = new StackX(MAX_NUM);
}
public void combine() {
newDS = new DataSet[MAX_NUM];
for (int i = 0; i < num * 2; i++) {
if (isBegin(elementArr[i])) {
stackImpl.push(elementArr[i]);

//System.out.println(“The element pushed is: ” + elementArr[i]);
} else {
int temp = stackImpl.pop();

if (stackImpl.isEmpty()) {

//System.out.println(“The current number of new data sets is: ” + k);
DataSet ds = new DataSet(temp, elementArr[i]);
//System.out.print(“[” + ds.begin + “, ” + ds.end + “]”);
newDS[k++] = ds;
}
}
}
}

public void displayNewDS() {
System.out.println(“All the new data sets are: “);

//System.out.println(“The size of newDS[] is: ” + newDS.length);

for (int i = 0; i < k; i++) {
System.out.print(“[” + newDS[i].begin + “, ” + newDS[i].end + “]”);
}

System.out.println();
}

public boolean isBegin(int i) {
for (int j = 0; j < num; j++) {
if (i == DSArr[j].begin) {
return true;
}
}

return false;
}

public void insert(int b, int e) {
DataSet ds = new DataSet(b, e);
DSArr[num++] = ds;
}

public void move() {
int j = 0;

for (int k = 0; k < num; k++) {
elementArr[j] = DSArr[k].begin;
j++;
elementArr[j] = DSArr[k].end;
j++;
}
}

public void displayDataSets() {
System.out.println(“All the data sets are: “);

for (int i = 0; i < num; i++) {
System.out.print(“[” + DSArr[i].begin + “, ” + DSArr[i].end + “]”);
System.out.print(” “);
}
System.out.println();
}

public void displayElements() {
System.out.println(“All the elements in datasets are: “);

for (int a = 0; a < num * 2; a++) {
System.out.print(elementArr[a] + ” “);
}

System.out.println();
}

public void quickSort(int left, int right) {
if (left >= right) {
return;
} else {
int pivot = elementArr[right];
int p = partition(left, right, pivot);
quickSort(left, p – 1);
quickSort(p + 1, right);
}
}

public int partition(int left, int right, int pivot) {
int lptr = left – 1;
int rptr = right;
while (true) {
while (elementArr[++lptr] < pivot) {
;
}

while (rptr > 0 && elementArr[–rptr] > pivot) {
;
}

if (lptr >= rptr) {
break;
} else {
swap(lptr, rptr);
}
}
swap(lptr, right);
return lptr;
}

public void swap(int l, int r) {
int temp;
temp = elementArr[l];
elementArr[l] = elementArr[r];
elementArr[r] = temp;
}
}

public class CombineIntervals {
public static void main(String[] args) {
int DataSetsNUM = 4;

DSArray dsa = new DSArray();
dsa.insert(2, 4);
dsa.insert(3, 7);
dsa.insert(1, 7);
dsa.insert(10, 18);
dsa.displayDataSets();
dsa.move();
dsa.quickSort(0, DataSetsNUM * 2 – 1);

dsa.displayElements();
dsa.combine();
dsa.displayNewDS();
}
}

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s