My Java Merge Sort Solution


  • 1
    S

    import java.util.ArrayList;

    class Building{
    int left;
    int ht;
    int right;

    Building(int left, int ht, int right){
    	this.left = left;
    	this.ht = ht;
    	this.right = right;
    }
    

    }

    class Strip{
    int left;
    int ht;

    Strip(int left, int ht){
    	this.left = left;
    	this.ht = ht;
    }
    

    }

    public class SkyLine {

    public static void main(String []args){
    	int arr[][] = {{1, 11, 5}, {2, 6, 7}, {3, 13, 9},
                {12, 7, 16}, {14, 3, 25}, {19, 18, 22},
                {23, 13, 29}, {24, 4, 28}};
    	
    	Building build[] = new Building[arr.length];
    	
    	for(int i = 0; i < arr.length; i++)
    		build[i] = new Building(arr[i][0], arr[i][1], arr[i][2]);
    	
    	ArrayList<Strip> res = findSkyline(build, 0, build.length-1);
    	
    	for(Strip s : res){
    		System.out.print("("+s.left+","+s.ht+") ");
    	}
    }
    
    static ArrayList<Strip> findSkyline(Building arr[], int l, int h){
    	if(l > h)
    		return null;
    	if(l == h){
    		ArrayList<Strip> res = new ArrayList<Strip>();
    		res.add(new Strip(arr[l].left, arr[l].ht));
    		res.add(new Strip(arr[l].right, 0));
    		return res;
    	}
    	int mid = (l + h) / 2;
    	
    	ArrayList<Strip> sl = findSkyline(arr, l, mid);
    	ArrayList<Strip> sr = findSkyline(arr, mid+1, h);
    	ArrayList<Strip> res = merge(sl, sr);
    	
    	return res;
    }
    
    static ArrayList<Strip> merge(ArrayList<Strip> a, ArrayList<Strip> b){
    
    	ArrayList<Strip> res = new ArrayList<Strip>();
    	int h1 = 0, h2 = 0, i = 0, j = 0;
    	
    	while((i < a.size()) && (j < b.size())){
    		Strip s1 = a.get(i), s2 = b.get(j);
    		if(s1.left < s2.left){
    			h1 = s1.ht;
    			if((res.size() > 0) && (res.get(res.size()-1).ht == Math.max(h1, h2))){
    				i++;
    				continue;
    			}
    			res.add(new Strip(s1.left, Math.max(h1, h2)));
    			i++;
    		} else{
    			h2 = s2.ht;
    			if((res.size() > 0) && (res.get(res.size()-1).ht == Math.max(h1, h2))){
    				j++;
    				continue;
    			}
    			res.add(new Strip(s2.left, Math.max(h1, h2)));
    			j++;
    		}
    	}
    	
    	while(i < a.size()){
    		res.add(a.get(i));
    		i++;
    	}
    	while(j < b.size()){
    		res.add(b.get(j));
    		j++;
    	}
    	return res;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.