UVA – 105 – SkyLine Problem

This is a brute force soloution that passed today but you can solve it using a sweep line
———————

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int[] w = new int[10005];

		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int a = in.nextInt(), W = in.nextInt(), b = in.nextInt();
			for (int i = a; i < b; i++)
				w[i] = Math.max(W, w[i]);
		}
		int y=0, a=-1, b = -1;
		for (int i = 0; i < 10000; i++) {
			if (y != w[i]) {
				if(a > 0) System.out.print(a +" "+ b + " ");
				y = w[i];
				a =i;
				b =y;
			}
		}
		System.out.println(a +" "+ b );
	}
}

Advertisements

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

%d bloggers like this: