Код сжат (несколько строк кода), что хорошо для турнира (время - самый дефицитный ресурс) и кажется правильным (я не знаю python, но думаю, что понимаю code).

Ваше решение в основном закрашивает горизонт города в буфере, а затем выводит содержимое буфера в требуемом формате.

Дополнительная информация, которую вы исключили из задачи, заключается в том, что будет не более 5000 зданий и горизонтальные позиции будут меньше 10.000. Это означает, что память не кажется проблемой в вашем случае (40 КБ для горизонта с 32-битной архитектурой плюс 45 КБ для описания здания - необязательно, вы можете нарисовать горизонт в цикле чтения). Алгоритм является линейным по количеству зданий, поэтому он работает быстро.

При более жестких ограничениях памяти вы можете выбрать однопроходный алгоритм,

Python: 115 символов

Как и OP, я не включаю объявление данных, но считаю пробелы.

D = [(1,11,5), (2,6,7), (3,13,9), (12,7,16), 
 (14,3,25), (19,18,22), (23,13,29), (24,4,28)]

P=[max([0]+[h for s,h,e in D if s<=x<e])for x in range(5001)]
for i,x in enumerate(P[1:]):
   if x!=P[i]:print i+1,x,

Обратите внимание, что я использую ссылку, предоставленную OP, как точное определение проблемы. Например, я немного обманываю, предполагая, что координаты здания не превышают 5000, и что все координаты являются положительными целыми числами. Исходный пост, на мой взгляд, недостаточно жестко ограничен, чтобы это было весело.

edit : спасибо Джону Пири за совет о сворачивании конструкции списка в цикл for печати. Как я это пропустил?!

редактировать : Я изменил диапазон (1 + max (zip (* D) [2])) на диапазон (5001) после принятия решения об использовании точного определения, данного в исходной задаче. Первая версия будет обрабатывать здания из произвольных положительных целых чисел (при условии, что все это умещается в памяти).

править : Понял, что я слишком усложняю. Проверьте мои исправления.

Кстати - у меня есть подозрение, что есть гораздо более элегантный и, возможно, более короткий способ сделать это. Кто-нибудь меня избил!

2 ответа C # - путь слишком длинный, но хотелось бы видеть лучше?

Подход LINQ (135 символов, исключая строку массива):

var a=new[]{new[]{1,11,5},new[]{2,6,7},new[]{3,13,9},new[]{12,7,16},new[]{14,3,25},new[]{19,18,22},new[]{23,13,29},new[]{24,4,28}};    
int l=0,y,x=-1;while(++x<5001){var b=a.Where(c=>c[0]<=x&&c[2]>x);if((y=b.Any()?b.Max(c=>c[1]):0)!=l)Console.Write(x+", "+(l=y)+", ");}

Или ответ без LINQ (179 185 символов, исключая строку массива):

var a={1,11,5,2,6,7,3,13,9,12,7,16,13,3,25,19,18,22,23,13,29,24,4,28};
var b=new int[5000];int i=-1,j,z;while(++i<a.Length)for(j=a[i*3];j<a[i*3+2];j++)if((z=a[i*3+1])>b[j])b[j]=z;i=-1;z=0;while(++i<5000)if(b[i]!=z)Console.Write(i+", "+(z=b[i])+", ");

98 символов J , неявно определенных (без имен переменных!):

,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0(([:<./{."1)}.[:i.@>:[:>./{:"1))

В действии:

$ jconsole
   s =: ,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0(([:<./{."1)}.[:i.@>:[:>./{:"1))
   |:b =: 8 3 $ 1 11 5 2 6 7 3 13 9 12 7 16 14 3 25 19 18 22 23 13 29 24 4 28
 1 2  3 12 14 19 23 24
11 6 13  7  3 18 13  4
 5 7  9 16 25 22 29 28
   s b
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Только 86 символов с предположением, что крайний левый координата всегда равна 1.

,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0([:>:[:i.[:>./{:"1))

Только 76 с дополнительным предположением, что самая правая координата не больше 99.

,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0&(>:i.99))

Заимствуя некоторые приемы у cobbal, я могу получить ее до 68.

[:,@({:"1#>:@i.@#,.{."1)[:1&|.[:(,.(~:_1&|.))[:>./(1&{*{.<:[:i.{:)"1

Молчаливое определение просто может: « Тем не менее, я стараюсь использовать s =:… для устранения избыточности.

Когда я отвечаю на вопрос с помощью J , я стараюсь найти время, чтобы объяснить, что происходит, потому что Я думаю, что другим может понравиться изучение работы чужого языка.

   NB. The first, second, and last element of a vector
   ({. 0{b), (1 { 0{b), ({: 0{b)
1 11 5
   NB. Count from 0 to (last element of vector)-1
   i. {: 0{b
0 1 2 3 4
   NB. Booleans: first element of vector less than or equal to (above)?
   ({. <: [:i.{:) 0{b
0 1 1 1 1
   NB. Multiply by second element of vector
   (1&{ * {.<:[:i.{:) 0{b
0 11 11 11 11
   NB. Stack up results for each vector, then find maximum by column
   >./ (1&{*{.<:[:i.{:) " 1 b
0 11 11 13 13 13 13 13 13 0 0 0 7 7 7 7 3 3 3 18 18 18 3 13 13 13 13 13 13
   NB. Identify leaders and make table
   |: (,. (~: _1 & |.)) >./(1&{*{.<:[:i.{:)"1 b
0 11 11 13 13 13 13 13 13 0 0 0 7 7 7 7 3 3 3 18 18 18 3 13 13 13 13 13 13
1  1  0  1  0  0  0  0  0 1 0 0 1 0 0 0 1 0 0  1  0  0 1  1  0  0  0  0  0
   NB. Rotate left
   |: 1 |. (,.(~:_1&|.))>./(1&{*{.<:[:i.{:)"1 b
11 11 13 13 13 13 13 13 0 0 0 7 7 7 7 3 3 3 18 18 18 3 13 13 13 13 13 13 0
 1  0  1  0  0  0  0  0 1 0 0 1 0 0 0 1 0 0  1  0  0 1  1  0  0  0  0  0 1
   NB. 1-based index and first element, when last element is true
   |: ({:"1 # >: @ i. @ # ,. {."1) 1&|.(,.(~:_1&|.))>./(1&{*{.<:[:i.{:)"1 b
 1  3 9 12 16 19 22 23 29
11 13 0  7  3 18  3 13  0
   NB. Flatten
   , ({:"1#>:@i.@#,.{."1)1&|.(,.(~:_1&|.))>./(1&{*{.<:[:i.{:)"1 b
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
   NB. Rearrange for tacit verb
   ([:,@({:"1#>:@i.@#,.{."1)[:1&|.[:(,.(~:_1&|.))[:>./(1&{*{.<:[:i.{:)"1) b
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Python со 133 символами , эффективными по памяти и времени, без ограничений на ввод данных

D = [(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)]

l,T=0,zip(*D)
for x,h in map(lambda x:(x,max([y for a,y,b in D if a<=x<b]or[0])),sorted(T[0]+T[2])):
    if h!=l: print x,h,
    l=h

объяснение:

lambda x:(x,max([y for a,y,b in D if a<=x<b]or[0])

возвращает позицию и высоту в позиции x.

Теперь переберите отсортированный список координат, составленный с помощью sorted (zip (* D) [0] + zip (* D) [2]) , и выведите, если высота изменится.

второй версия не так эффективна, как предыдущая, и имеет ограничение по координатам, но использует только 115 символов :

for x in range(100):
    E=[max([y for a,y,b in D if a<=(x-i)<b]+[0])for i in(0,1)]
    if E[0]-E[1]:print x,E[0],

Python, 89 символов, также используется чит-код 5001 от Triptych:

B=[[1,11,5],[2,6,7],[3,13,9],[12,7,16],[14,3,25],[19,18,22],[23,13,29],[24,4,28]]

x=o=0
while x<5001:
 n=max([H for L,H,R in B if L<=x<R]+[0])
 if n-o:print x,n,
 o=n;x+=1

Замена 5001 на max (map (max, B)) + 1 чтобы разрешить (почти) произвольно большие города, оставляет 102 символа.

История изменений:

• сохранил два символа, как описано в комментарии Джона Пири
• , сохранил один символ, как предложил MahlerFive

Помимо задачи

Правильный ли набор результатов? В позиции 22 наивысшая точка - 18, а в позиции 23 - 13, так что 3 - не самая высокая точка.

Я также пытался сделать версию для php, и она дает мне другой конечный вектор. Он не оптимизирован для скорости.

<?php
$buildings = array(
    array(1,11,5), 
    array(2,6,7), 
    array(3,13,9), 
    array(12,7,16), 
    array(14,3,25), 
    array(19,18,22), 
    array(23,13,29), 
    array(24,4,28)
);

$preSkyline = array();
for( $i = 0; $i<= 30; $i++){
    foreach( $buildings as $k => $building){
        if( $i >= $building[0] && $i<= $building[2]){
            $preSkyline[$i][$k] = $building[1];
        } else{
            $preSkyline[$i][$k] = 0;
        }
    }
}
foreach( $preSkyline as $s =>$a){
    $skyline[$s] = max( $a );
}
$finalSkyline = array();
foreach( $skyline as $k => $v){
    if( $v !== $skyline[ $k-1]){
        $finalSkyline[$k] =  $v;
    }
}
echo "<pre>";
print_r( $finalSkyline );
?>

это возвращает:

Array
(
    [0] => 11
    [2] => 13
    [9] => 0
    [11] => 7
    [16] => 3
    [18] => 18
    [22] => 13
    [29] => 0
)

, которые являются точками перегиба и максимальной высотой.

Вот моя попытка на Perl. 137 символов, из которых 33 предназначены для поиска конца линии горизонта.

@a = ([1,11,5],[2,6,7],[3,13,9],[12,7,16],[14,3,25],[19,18,22],[23,13,29],[24,4,28]);
($x)=sort{$b<=>$a}map{$$_[2]}@a;
for(;$c<=$x;$c++){$n=0;map{$n=$$_[1]if$c>=$$_[0]&&$c<$$_[2]&&$n<$$_[1]}@a;print"$c $n "if$n!=$h;$h=$n;}

176-байтовый исполняемый файл WinXP .COM:

vQoAgMYQjsKO2jPAM / + 5AIDzq7QLzSE8 / 751AXQDvoQB6DkAi / noNACL2egvACn5A / 87HXYCiR2D xwLi9eviM8mZ9 / VSQQvAdfeI + rQCzSG3LFqAwjC0As0h4vbD / 9Y8CnP6D7bI / 9Y8CnPwtACR9 + UD yOvxtAvNITz / dRO0CM0hLDDDtAHNITwadfW + kAHDM / Yz / 7cgrTn4dA + L + I1E / tHo6Jr / i8folf8L 9nXozSA =

в кодировке Base64, я использовал этот сайт для его кодирования . Расшифровать в файл .com. Программа читает stdin до EOF, который является Ctrl-Z при чтении с консоли, а затем выводит результат на stdout.

EDIT: Исходный код:

    mov bp,10
    add dh,10h
    mov es,dx
    mov ds,dx
    xor ax,ax
    xor di,di
    mov cx,8000h
    rep stosw
    mov ah,0bh
    int 21h
    cmp al,255
    mov si,offset l9
    je l1
    mov si,offset l11
l1:
    call l7
    mov di,cx
    call l7
    mov bx,cx
    call l7
    sub cx,di
    add di,di
l2:
    cmp bx,[di]
    jbe l3
    mov [di],bx
l3:
    add di,2
    loop l2
    jmp l1
l4:
    xor cx,cx
l5:
    cwd
    div bp
    push dx
    inc cx
    or ax,ax
    jnz l5
    mov dl,bh
    mov ah,2
    int 21h
    mov bh,44
l6:
    pop dx
    add dl,48
    mov ah,2
    int 21h
    loop l6
    ret
l7:
    call si
    cmp al,10
    jae l7
    db 0fh, 0b6h, 0c8h
l8:
    call si
    cmp al,10
    jae ret
    mov ah,0
    xchg cx,ax
    mul bp
    add cx,ax
    jmp l8
l9:
    mov ah,0bh
    int 21h
    cmp al,255
    jne l12
    mov ah,8
    int 21h
l10:
    sub al,48
    ret
l11:
    mov ah,1
    int 21h
    cmp al,26
    jne l10
    mov si,offset l12
    ret
l12:
    xor si,si
    xor di,di
    mov bh,32
l13:
    lodsw
    cmp ax,di
    je l14
    mov di,ax
    lea ax,[si-2]
    shr ax,1
    call l4
    mov ax,di
    call l4
l14:
    or si,si
    jne l13
    int 20h

Скомпилирован, как обычно для меня, с использованием A86.

Rereading the UVA rules, we're not limited to a max X of 5000, but rather 5000 buildings. X and Y values up to (and including) 9999 are allowed.

Also, apparently only C, C++, C#, and Java are officially recognized languages, so I did mine up in Java. The numbers are only space separated, but commas could be put back in (at a cost of two more total chars). Totalling 153 chars (excluding the array line):

int[][]b=new int[][]{{1,11,5},{2,6,7},{3,13,9},{12,7,16},{14,3,25},{19,18,22},{23,13,29},{24,4,28}};
int[]y=new int[10000];int i;for(int[]o:b)for(i=o[0];i<o[2];y[i]=Math.max(y[i++],o[1]));for(i=0;i<9999;)if(y[i++]!=y[i])System.out.print(i+" "+y[i]+" ");

The logic is pretty straightforward. The only things that make the flow a little wonky are variable reuse and nonstandard placement of post-increment. Generates:

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0 

Вот быстрый пример на Perl

(под быстрым я подразумеваю менее двух часов)

Perl всего с 327 символами

(исключая " # / ] "для улучшения выделения)

use 5.010;
$/=undef;
@s=map{[split',',$_]}grep{$_}split/\)\s*(?:$|,\s*\()|^\s*\(/,<>; #/
for$s(@s){($l,$y,$r)=@$s;
for$x($l..$r){$c=$p[$x];$p[$x]=$c>$y?$c:$y;}}
for($x=1;$x<=@p;$x++){$y=$p[$x]||0;
if(!defined$z){$l=$x;$z=$y;
}elsif($y!=$z){push@n,[$l,$z,$x-1];$z=$y;$l=$x;}}
push@n,[$l,$z];
say join', ',map{($_->[0],$_->[1])}@n;

Исходная тестовая версия 853 символа

#! /usr/bin/env perl
use strict;
use warnings;
use 5.010;
use YAML;
use List::Util 'max';


my $file;
{
  local $/ = undef;
  $file = <>;
}

my @sections = map { [split ',', $_] } grep {$_} split m'
  \)\s* (?:$|,\s*\() |
  ^ \s* \(
'x, $file;

#my $max_x = max map{ $_->[2] } @sections;
#say $max_x;

my @points;
for my $reg( @sections ){
  my($l,$y,$r) = @$reg;
  for my $x ( $l .. $r ){
    my $c = $points[$x] || 0;
    $points[$x] = max $c, $y;
  }
}


my @new;
my($l,$last_y);
for( my $x=1; $x <= @points; $x++ ){
  my $y = $points[$x] || 0;

  # start
  if( ! defined $last_y ){
    $l = $x;
    $last_y = $y;
    next;
  }

  if( $y != $last_y ){
    push @new, [$l,$last_y,$x-1];
    $last_y = $y;
    $l = $x;
    next;
  }
}
push @new, [$l,$last_y];


say Dump \@sections, \@points, \@new;

say join ', ', map { ($_->[0],$_->[1]) } @new;

Начальная уменьшенная версия 621 символ

(исключая« # / »для улучшения выделения)

#! /usr/bin/env perl
use strict;
use warnings;
use YAML;
use 5.010;

$/=undef;

my@s=map{[split',',$_]}grep{$_}split/\)\s*(?:$|,\s*\()|^\s*\(/,<>; #/

my@p;
{
  no strict; no warnings 'uninitialized';

  for$s(@s){
    ($l,$y,$r)=@$s;
    for$x($l..$r){
      $c=$p[$x];
      $p[$x]=$c>$y?$c:$y;
    }
  }
}

# $last_y => $z
my @n;
{
  no strict;

  #my($l,$z);
  for($x=1;$x<=@p;$x++){
    $y=$p[$x]||0;
    if(!defined$z){
      $l=$x;
      $z=$y;
    }elsif($y!=$z){
      push@n,[$l,$z,$x-1];
      $z=$y;
      $l=$x;
    }
  }
  push@n,[$l,$z];
}

say Dump \@s, \@p, \@n;

say join', ',map{($_->[0],$_->[1])}@n;

Я использовал YAML , чтобы убедиться, что я получаю правильные данные, и что разные версии работают одинаково.

При условии ввода:

b=[(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)]

Haskell: 105 символов

h x=maximum$0:[y|(l,y,r)<-b,l<=x,x<r]
main=putStr$unwords[show x++" "++show(h x)|x<-[1..9999],h x/=h(x-1)]

Форматирование строк, похоже, является тем местом, где Haskell отстает от решений Python. Необходимость использовать дополнительные 5 символов для записи 'main =' тоже не помогает, но, возможно, это не стоит включать, решения C # / Java были бы огромными, если бы их код должен был демонстрировать полную программу :)

Haskell: 76 символов (без форматирования строк и без main)

h x=maximum$0:[y|(l,y,r)<-b,l<=x,x<r]
print[(x,h x)|x<-[1..9999],h x/=h(x-1)]

Оглядываясь на исходную проблему , она требует, чтобы вы читали ввод из файла, поэтому я подумал, что было бы интересно посмотрим, сколько знаков это добавит.

Haskell: 149 символов (полное решение)

main=interact f
f i=unwords[show x++" "++show(h x)|x<-[1..9999],h x/=h(x-1)] where
 h x=maximum$0:[y|[l,y,r]<-b,l<=x,x<r]
 b=map(map read.words)$lines i

Ниже показано, как выглядит полное решение с более информативными именами переменных и сигнатурами типов, где это возможно.

main :: IO ()
main = interact skyline

skyline :: String -> String
skyline input =

  unwords [show x ++ " " ++ show (heightAt x) |
           x <- [1..9999], heightAt x /= heightAt (x-1)]

  where heightAt :: Int -> Int
        heightAt x = maximum $ 0 : [h | [l,h,r] <- buildings, l <= x, x < r]

        buildings :: [[Int]]
        buildings = map (map read . words) $ lines input