public int[][] merge(int[][] a) {
  	//1. 先去除a为空的情况
  	if(a.length==0)return new int[][]{};
  	Integer[][] intervals = new Integer[a.length][a[0].length];
  	//2. 为了方便排序，将其转换为Integer数组
  	cpy(a, intervals);
  	
  	//3. 排序
  	Arrays.sort(intervals, new Comparator<Integer[]>() {

	   @Override
              public int compare(Integer[] x, Integer[] y) {
                  if(x[0] < y[0]){
                      return -1;
                  } else if(x[0] > y[0]){
                      return 1;
                  } else {
                      return 0;
                  }
              }

});
//4. 遍历查找是否相交
  	ArrayList<Integer[]> list = new ArrayList<>();
  	for(int i=0;i<intervals.length;i++) {
  		int j = i;
  		Integer[] tIntegers = new Integer[2];
  		tIntegers[0] = intervals[i][0];
  		tIntegers[1] = intervals[i][1];
  		//有相交的情况
  		while(i+1<=intervals.length-1&&intervals[i+1][0]<=tIntegers[1]) {
  			if(intervals[i+1][1]>tIntegers[1]) {
  				tIntegers[1] = intervals[i+1][1];
  			}
  			i++;
  		}
  		
  		list.add(tIntegers);
  	}
  	//5. 转换为int[][]返回
  	int[][] res = new int[list.size()][2];
  	for(int i=0;i<list.size();i++) {
  		Integer[] integers = list.get(i);
  		res[i][0] = integers[0];
  		res[i][1] = integers[1];
  	}
return res;
  }

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
    	ArrayList<Integer> list = new ArrayList<>();
    	
    	int i=0,j=0;
    	int n=matrix.length;
        if(n==0)return list;
    	int m = matrix[0].length;
    	int cnt = 0,loop=0;
    	while(cnt<m*n) {
    		while(cnt<n*m&&j<m-loop) {
    			list.add(matrix[i][j]);
    			cnt++;
    			j++;
    		}
    		
    		j--;
    		i++;
    		
    		while(cnt<m*n&&i<n-loop) {
    			list.add(matrix[i][j]);
    			
    			i++;
    			cnt++;
    		}
    		
    		i--;
    		j--;
    		
    		while(cnt<m*n&&j>=loop) {
    			list.add(matrix[i][j]);
    			cnt++;
    			j--;
    		}
    		j++;
    		i--;
    		
    		while(cnt<m*n&&i>loop) {
    			list.add(matrix[i][j]);
    			i--;
    			cnt++;
    		}
    		i++;
    		j++;
    		loop++;
    		//System.out.println(list);
    	}
    	
		return list;
        
    }
}

  public List<Integer> spiralOrder(int[][] matrix) {
  	ArrayList<Integer> list = new ArrayList<>();
  	
  	int i=0,j=0;
  	int m=matrix.length;
      if(m==0)return list;
  	int n = matrix[0].length;
  	int cnt = 0,loop=0;
  	while(cnt<m*n) {
  		i=loop;
  		j=loop;
  		for(int k=j; k<n-loop;k++,cnt++) {
  			list.add(matrix[i][k]);
  		}
  		j += n-loop-1;
  		
  		for(int k=i+1;k<m-loop;k++,cnt++) {
  			list.add(matrix[k][j]);
  		}
  		i += m-loop-1;
  		for(int k=j-1; k>=loop;k--,cnt++) {
  			list.add(matrix[i][k]);
  		}
  		j = loop;
  		for(int k=i-1;k>loop;k--,cnt++) {
  			list.add(matrix[k][j]);
  		}
  		
  		loop++;
  		//System.out.println(list);
  	}
  	
return list;
      
  }

  public List<Integer> spiralOrder(int[][] matrix) {
  	ArrayList<Integer> list = new ArrayList<>();
  	
  	int i=0,j=0;
  	int m=matrix.length;
      if(m==0)return list;
  	int n = matrix[0].length;
  	
  	int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
  	int idx = 0;
  	for(int k=0;k<m*n;k++) {
  		
  		list.add(matrix[i][j]);
  		matrix[i][j] = 1000;
  		int x = i + dirs[idx][0];
  		int y = j + dirs[idx][1];
  		if(x<0 || y<0 || x>=m || y>=n || (matrix[x][y]^1000)==0) {
  			idx = (idx + 1)%4;
  			x = i + dirs[idx][0];
  			y = j + dirs[idx][1];
  		}
  		i=x;
  		j=y;
  	}
  	
return list;
      
  }

public void rotate(int[][] matrix) {
    int[][] tmp = new int[matrix.length][matrix.length];
	for(int i=0;i<matrix.length;i++) {
		for(int j=0;j<matrix.length;j++) {
			tmp[i][j] = matrix[i][j];
		}
	}
	for(int i=0;i<matrix.length;i++) {
		for(int j=0;j<matrix.length;j++) {
			matrix[j][matrix.length-i-1] = tmp[i][j];
		}
	
	}
}