package com.dam.lineCombine;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
public class LineCombine {
    public static void main(String[] args) {
        List<int[]> lineList = new ArrayList<>();
        Random random = new Random();
        for (int i = 0; i < 5; i++) {
            int start = random.nextInt(10);
            int[] arr = {start, start + random.nextInt(3) + 1};
            lineList.add(arr);
        }
        LineCombine lineCombine = new LineCombine();
        lineCombine.printLineList(lineList);
        lineCombine.lineCombine(lineList);
        System.out.println("------------------------------------------");
        lineCombine.printLineList(lineList);
    }
    public void printLineList(List<int[]> lineList) {
        for (int[] ints : lineList) {
            System.out.println(Arrays.toString(ints));
        }
    }
    /**
     * 线投影
     *
     * @param lineList
     * @return
     */
    public void lineCombine(List<int[]> lineList) {
        //将线升序排序
        this.quickSort(lineList, 0, lineList.size() - 1);
        int i = 0, j;
        while (i < lineList.size() - 1) {
            j = i + 1;
            while (j < lineList.size()) {
                if (lineList.get(i)[1] >= lineList.get(j)[0]) {
                    if (lineList.get(j)[1] <= lineList.get(i)[1]) {
                        lineList.remove(j);
                    } else {
                        lineList.get(i)[1] = lineList.get(j)[1];
                        lineList.remove(j);
                    }
                } else {
                    i++;
                    break;
                }
            }
        }
    }
    /**
     * 快速排序
     *
     * @param layerNumLimitSegmentList
     */
    private void quickSort(List<int[]> layerNumLimitSegmentList, int left, int right) {
        int l = left; //左下标
        int r = right; //右下标
        //pivot 中轴值
        int pivot = layerNumLimitSegmentList.get((left + right) / 2)[0];
        int[] temp; //临时变量，作为交换时使用
        //while循环的目的是让比pivot 值小放到左边
        //比pivot 值大放到右边
        while (l < r) {
            //在pivot的左边一直找,找到大于等于pivot值,才退出
            while (layerNumLimitSegmentList.get(l)[0] < pivot) {
                l += 1;
            }
            //在pivot的右边一直找,找到小于等于pivot值,才退出
            while (layerNumLimitSegmentList.get(r)[0] > pivot) {
                r -= 1;
            }
            //如果l >= r说明pivot 的左右两的值，已经按照左边全部是
            //小于等于pivot值，右边全部是大于等于pivot值
            if (l >= r) {
                break;
            }
            //交换
            temp = layerNumLimitSegmentList.get(l).clone();
            layerNumLimitSegmentList.set(l, layerNumLimitSegmentList.get(r));
            layerNumLimitSegmentList.set(r, temp);
            //如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移
            if (layerNumLimitSegmentList.get(l)[0] == pivot) {
                r -= 1;
            }
            //如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
            if (layerNumLimitSegmentList.get(r)[0] == pivot) {
                l += 1;
            }
        }
        // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归，把左边变成有序的
        if (left < r) {
            quickSort(layerNumLimitSegmentList, left, r);
        }
        //向右递归，把右边变成有序的
        if (right > l) {
            quickSort(layerNumLimitSegmentList, l, right);
        }
    }
}

package com.dam.lineCombine;
import java.util.Arrays;
import java.util.Random;
public class LineCombineForArr {
    public static void main(String[] args) {
        int lineNum = 5;
        int[][] lineArr = new int[lineNum][2];
        Random random = new Random();
        for (int i = 0; i < lineNum; i++) {
            int start = random.nextInt(10);
            int[] arr = {start, start + random.nextInt(3) + 1};
            lineArr[i] = arr;
        }
        LineCombineForArr lineCombine = new LineCombineForArr();
        System.out.println("给定n条线段--------------------------------");
        lineCombine.printLineArr(lineArr,lineArr.length);
        System.out.println("投影后的线段--------------------------------");
        lineCombine.lineCombine(lineArr);
    }
    public void printLineArr(int[][] lineArr,int printLen) {
        for (int i = 0; i < printLen; i++) {
            System.out.println(Arrays.toString(lineArr[i]));
        }
    }
    /**
     * 线投影
     *
     * @param lineArr
     * @return
     */
    public void lineCombine(int[][] lineArr) {
        //将线升序排序
        this.quickSort(lineArr, 0, lineArr.length - 1);
        int i = 0, j, lineArrLen = lineArr.length;
        while (i < lineArrLen - 1) {
            j = i + 1;
            while (j < lineArrLen) {
                if (lineArr[i][1] >= lineArr[j][0]) {
                    if (lineArr[j][1] <= lineArr[i][1]) {
                        for (int k = j; k < lineArrLen - 1; k++) {
                            lineArr[k] = lineArr[k + 1];
                        }
                        lineArrLen-=1;
                    } else {
                        lineArr[i][1] = lineArr[j][1];
                        for (int k = j; k < lineArrLen - 1; k++) {
                            lineArr[k] = lineArr[k + 1];
                        }
                        lineArrLen-=1;
                    }
                } else {
                    i++;
                    break;
                }
            }
        }
        this.printLineArr(lineArr,lineArrLen);
    }
    /**
     * 快速排序
     *
     * @param layerNumLimitSegmentArr
     */
    private void quickSort(int[][] layerNumLimitSegmentArr, int left, int right) {
        int l = left; //左下标
        int r = right; //右下标
        //pivot 中轴值
        int pivot = layerNumLimitSegmentArr[(left + right) / 2][0];
        int[] temp; //临时变量，作为交换时使用
        //while循环的目的是让比pivot 值小放到左边
        //比pivot 值大放到右边
        while (l < r) {
            //在pivot的左边一直找,找到大于等于pivot值,才退出
            while (layerNumLimitSegmentArr[l][0] < pivot) {
                l += 1;
            }
            //在pivot的右边一直找,找到小于等于pivot值,才退出
            while (layerNumLimitSegmentArr[r][0] > pivot) {
                r -= 1;
            }
            //如果l >= r说明pivot 的左右两的值，已经按照左边全部是
            //小于等于pivot值，右边全部是大于等于pivot值
            if (l >= r) {
                break;
            }
            //交换
            temp = layerNumLimitSegmentArr[l].clone();
            layerNumLimitSegmentArr[l] = layerNumLimitSegmentArr[r];
            layerNumLimitSegmentArr[r] = temp;
            //如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移
            if (layerNumLimitSegmentArr[l][0] == pivot) {
                r -= 1;
            }
            //如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
            if (layerNumLimitSegmentArr[r][0] == pivot) {
                l += 1;
            }
        }
        // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归，把左边变成有序的
        if (left < r) {
            quickSort(layerNumLimitSegmentArr, left, r);
        }
        //向右递归，把右边变成有序的
        if (right > l) {
            quickSort(layerNumLimitSegmentArr, l, right);
        }
    }
}