Perpanjang interval integer secara maksimal

14

Misalkan Anda diberi satu set interval integer yang tidak memotong[a1,b1],[a2,b2],[a3,b3],...,[aN,bN] . (Di mana [a,b]himpunan bilangan bulat lebih besar dari atau sama dengan adan kurang dari atau sama dengan b.)

Interval pada indeks Xmencakup bX - aX + 1nilai. Kami akan memanggil nomor ini cX.

Mengingat bahwa setiap interval dapat ...

  • tidak berubah (tetap sebagai [aX,bX]),
  • meluas ke kanan menuju +sisi nomor garis dengan cX(menjadi [aX,bX + cX])
  • atau meluas ke kiri ke -sisi nomor garis dengan cX(menjadi [aX - cX,bX]),

berapakah jumlah nilai maksimum yang dapat dicakup oleh penyatuan semua interval yang diperbarui, mengingat bahwa semuanya masih non-berpotongan?

Tulis fungsi atau program yang mengambil string dari formulir [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]dan hitung maksimum ini. Jika menulis fungsi, kembalikan nilainya. Jika menulis program lengkap, gunakan stdin untuk input dan cetak nilai ke stdout (atau gunakan alternatif terdekat).

Anda dapat mengasumsikan semua nilai berada dalam batas integer 32-bit bertanda normal dan itu aXkurang dari atau sama dengan bXuntuk semua indeks X. Interval mungkin dalam urutan apa pun, mereka tidak selalu selalu meningkat. Mereka harus diberikan sebagai string dalam format di atas. String mungkin kosong, dalam hal ini jawabannya adalah 0.

Pengajuan terpendek dalam byte menang.

Contoh

Jika inputnya adalah [-3,0],[1,2],[4,9]output akan menjadi 22. Interval tengah tidak memiliki ruang untuk memperluas kedua cara sehingga harus tetap tidak berubah. Interval kiri dan kanan dapat diperpanjang ke [-7,0]dan [4,15]masing - masing. Penyatuan [-7,0]dan [1,2]dan [4,15]berisi semua nilai dari -7 hingga 15, kecuali 3. Itu adalah 22 nilai.

code-golf set-theory Hobi Calvin
sumber
3
Bisakah kita menggunakan representasi string asli array bahasa kita untuk input, atau apakah harus persis format ini?
Martin Ender
@ MartinBüttner No. Anda harus menggunakan format yang tepat ini. (Aku tahu itu semacam pedang bermata dua tapi itulah caranya.)
Calvin's Hobbies
Bisakah Anda memperluas interval yang diberikan di kedua sisi? Misalnya, dapat [5,6]menjadi [3,8](untuk jawaban 6), atau bisa adil [5,8]atau [3,6](untuk jawaban 4)?
MtnViewMark
@MtnViewMark No. Mereka hanya dapat diperpanjang dari satu sisi (atau tidak sama sekali)
Calvin's Hobbies

Jawaban:

4

Haskell, 145 byte

import Data.List
x=maximum.map length.filter(nub>>=(==)).map concat.sequence.map(\[a,b]->[[2*a-b-1..b],[a..b],[a..2*b-a+1]]).read.('[':).(++"]")

Sampel berjalan:

λ: x ""
0

λ: x "[5,6]"
4

λ: x "[-3,0],[1,2],[4,9]"
22
MtnViewMark
sumber
1

R, 282 278 269 247

Ini menjadi sangat besar sangat cepat berurusan dengan input string. Saya kira saya bisa bermain golf ini lebih baik, tetapi saat ini kehabisan waktu.

f=function(s){i=matrix(strtoi(strsplit(gsub('[^0-9,-]','',s),',')[[1]]),nrow=2);l=0;if((a<-length(b<-order(i[1,])))>0){if(a>1)i=i[,b];l=diff(i[,1:a])+1;x=c(t(i));for(n in 1:a)if(n==1|n==a|x[n]-l[n]>x[n+a-1]|x[n+a]+l[n]<x[n+1])l[n]=l[n]*2;};sum(l)}

Intinya idenya adalah

  • Ambil string dan mengubahnya menjadi matriks 2 baris
  • Pastikan itu dalam urutan yang benar
  • Tentukan perbedaan untuk setiap kolom
  • Gandakan perbedaan pertama dan terakhir
  • Gandakan perbedaan tengah jika mereka memiliki kesenjangan dengan sebelumnya atau berikutnya yang cukup besar
  • Kembalikan jumlah perbedaan

Sunting: menyadari Saya awalnya salah menghitung karakter, lalu mengatur ulang beberapa hal untuk mencukur beberapa.

MickyT
sumber