Back
Close
Employers: discover CodinGame for tech hiring
EVENTS
UPCOMINGPAST
SOLO
PUZZLESCODE GOLFOPTIMIZATION
MULTI
LEADERBOARDSCLASH OF CODEBOT PROGRAMMINGCODING ESCAPE
COMMUNITY
CONTRIBUTIONSLEARNDISCORDFORUMLIVE STREAMS

Skylines

Statement

 Goal

Count the number of lines needed to draw the skyline of a city.

The city skyline (or silhouette) as seen from a distance consists of a series of buildings with rectangular shape which might overlap each other.
Each building is described by its height (h) above ground level and the horizontal position of the left (x1) and right (x2) walls.

Line drawing rules:

To draw the skyline of a city with a single building 3 lines are required: One for the left wall, one for the roof and one for the right wall.
      ____
     |    |
     |    |
     |    |

Two separate buildings can be drawn using 7 lines: 3 lines for each of the two buildings and one line connecting the buildings on ground level.
      ____
     |    |      ______
     |    |     |      |
     |    |_____|      |

Two partially overlapping or adjacent buildings of different heights require 5 lines to be drawn. One for the left wall of the first building, two for the roofs, one for the wall connecting the roofs and one for the right wall of the second building.
The dotted lines in the picture below show the actual shape of the two buildings.
      ____
     |    |____
     |  ¦¨¦    |
     |  ¦ ¦    |

Two buildings are called adjacent (i.e. touching each other) if their opposing walls have the same horizontal position.
Input
Line 1: An integer n for the number of buildings in the city.
Next n lines: Three space separated integers h, x1 and x2 for the height and the two positions of the walls respectively.

The buildings are given in no particular order.
Output
One line containing the number of lines needed to draw the city skyline.
Constraints
1 ≤ n ≤ 100
1 ≤ h ≤ 200
0 ≤ x1 < x2 ≤ 5000
Example
Input
1
10 100 110
Output
3
Tags
Difficulty
Very Hard
Test cases
Single building Test
Input
1 10 100 110
Output
3
Validator 1 Validator
Input
1 20 150 200
Output
3
2 separate buildings Test
Input
2 10 100 110 20 200 210
Output
7
Validator 2 Validator
Input
2 20 1100 2110 10 2200 2210
Output
7
2 adjacent buildings Test
Input
2 50 300 320 20 250 300
Output
5
Validator 3 Validator
Input
2 150 300 320 120 250 300
Output
5
2 overlapping buildings Test
Input
2 30 100 300 70 180 200
Output
7
Validator 4 Validator
Input
2 50 200 350 60 280 310
Output
7
3 connected buildings Test
Input
3 40 1000 1200 60 900 1010 40 1100 1300
Output
5
Validator 5 Validator
Input
3 30 2000 3000 160 1500 2100 30 2500 5000
Output
5
Lots of overlap Test
Input
10 164 3292 4280 164 3996 4655 9 491 4924 9 491 4924 52 1389 4655 135 2059 4924 52 3996 4924 9 491 4280 22 3996 4924 151 1389 3292
Output
9
Validator 6 Validator
Input
10 194 1223 2762 140 1158 4720 26 1447 3605 26 269 4720 26 269 2762 26 2762 4410 108 2762 4410 26 1158 4720 108 4410 4720 68 269 2377
Output
9
Separation Test
Input
10 53 4505 4548 22 2217 2240 164 4046 4224 16 4037 4224 124 1751 1927 155 4046 4111 40 414 690 156 2969 3055 28 2240 2426 156 2512 2526
Output
31
Validator 7 Validator
Input
10 45 21 34 86 2429 2488 151 4710 4724 65 3050 3269 38 745 815 162 3269 3308 184 534 576 97 3260 3610 142 2300 2488 34 4215 4382
Output
33
Big city Test
Input
25 196 1668 1753 37 555 687 129 214 308 114 3242 3249 117 3016 3242 14 753 1157 155 89 218 14 3150 3242 184 3242 3283 9 10 53 187 3565 3767 120 63 89 174 2619 2824 120 687 1042 98 3271 3565 37 3249 3396 167 4663 4728 114 3025 3150 157 3869 4007 23 4738 4862 171 10 63 114 1775 1860 13 468 555 157 320 476 110 2527 2643
Output
57
Validator 8 Validator
Input
25 172 1758 2076 73 3187 3377 135 2550 2949 21 4556 4710 109 298 437 92 3887 3995 146 901 991 56 1630 1682 32 3995 4039 169 4883 4959 178 599 901 43 1758 1842 48 3887 4005 32 1682 1758 72 3070 3187 21 4872 4959 147 1287 1402 54 1062 1286 166 2700 2996 49 2393 2726 152 2090 2393 134 1849 2076 34 2340 2550 152 4587 4752 60 3128 3187
Output
61
Bigger city Test
Input
50 6 4648 4854 166 2648 2709 68 2853 2883 112 4138 4266 166 4242 4292 68 3818 3897 168 1436 1483 177 4396 4419 6 24 251 177 1419 1436 116 1350 1362 136 661 670 116 713 834 87 1287 1378 116 2488 2574 87 3582 3611 166 2261 2296 173 950 1001 146 3402 3426 34 461 487 177 24 166 116 2853 3022 34 2125 2296 165 4570 4661 27 2435 2461 44 3404 3435 195 635 733 177 1362 1396 177 410 557 68 3622 3758 176 2983 3105 177 1 24 116 2342 2360 27 2315 2326 87 733 842 177 3319 3342 173 196 394 166 661 713 44 3130 3154 166 2804 3016 34 3897 3931 166 3402 3435 87 1027 1208 6 4242 4292 165 3016 3105 24 3931 3968 136 3447 3611 131 1100 1113 165 2060 2142 27 1 24
Output
123
Validator 9 Validator
Input
50 184 3129 3141 73 1168 1209 101 4861 4923 70 306 328 70 4515 4586 192 3905 3976 80 539 562 135 996 1126 46 3649 3660 194 4515 4586 177 4829 4861 177 3216 3285 135 194 261 80 2836 2848 80 286 337 46 2690 2745 113 593 725 120 1414 1470 80 378 539 194 4103 4104 99 4125 4161 192 3115 3168 135 4103 4104 189 2189 2386 135 4515 4620 192 1172 1241 70 1807 1922 97 2990 3099 189 4717 4769 99 578 670 97 3844 3976 113 3844 4034 46 2836 2849 97 4625 4708 192 254 328 160 3163 3216 189 1409 1448 113 4161 4174 189 3844 3905 177 4174 4222 192 3223 3257 194 3285 3301 99 1136 1209 115 1133 1209 99 3801 3976 120 4122 4165 6 2033 2103 184 3301 3312 80 1804 1807 112 352 406
Output
125
Metropolis Test
Input
100 101 1745 1873 1 3977 4064 183 1089 1152 1 4436 4479 21 4847 4972 88 3946 4064 118 3168 3180 61 3200 3300 151 4668 4683 159 4436 4576 107 1465 1481 96 1365 1463 117 2457 2466 114 1683 1690 87 287 383 131 540 657 131 3655 3746 42 2965 3025 23 1343 1373 64 403 485 98 4124 4175 131 689 754 118 1873 1923 177 3791 3875 107 214 309 60 1465 1481 185 2408 2457 117 2503 2557 98 2748 2795 197 2460 2466 52 1470 1488 152 301 485 64 2346 2359 114 1071 1169 159 2298 2312 52 2620 2625 196 403 483 52 534 657 23 3619 3692 131 2911 2941 159 1481 1546 34 1123 1169 46 2710 2773 29 2620 2625 87 4355 4357 197 1373 1476 88 485 553 131 923 928 113 3831 3922 143 1640 1658 184 3534 3655 169 2565 2638 155 4911 4973 23 3212 3467 114 4879 4972 151 1653 1707 35 3031 3108 34 3485 3541 118 4007 4023 113 91 126 29 4543 4595 155 1270 1292 99 4335 4395 131 1683 1698 193 877 971 169 2391 2466 183 4668 4679 130 4258 4387 197 2915 2962 21 4683 4705 152 1667 1674 87 2986 3071 87 4189 4355 24 1923 1929 101 2948 3025 118 1272 1338 172 3799 3811 193 3180 3212 143 4077 4146 117 1707 1842 21 4395 4517 60 3760 3811 88 993 1071 172 923 1001 42 3799 3870 58 4357 4436 159 1481 1507 107 1251 1272 150 3161 3200 35 27 91 172 4128 4181 197 3168 3212 61 2911 2915 1 3031 3108 64 2557 2607 169 2359 2391 149 3804 3922 114 174 178 52 4181 4189 35 3692 3734
Output
191
Validator 10 Validator
Input
100 55 3109 3125 53 4732 4779 125 2286 2366 200 3764 3806 187 2429 2578 63 1746 1794 135 4644 4697 195 1094 1182 54 2035 2139 121 624 689 8 4756 4760 77 556 591 77 4645 4697 9 3730 3820 195 4517 4585 113 2729 2787 54 2081 2139 89 4097 4111 43 3179 3238 150 3239 3356 89 4120 4175 99 2070 2139 195 1557 1597 28 924 1027 127 4682 4717 11 2541 2627 11 3113 3117 89 2106 2189 9 1493 1569 11 244 450 79 1224 1265 53 2848 2887 5 4517 4563 31 238 455 99 924 991 22 4756 4815 58 4215 4314 120 1967 2087 38 1628 1675 104 1182 1221 127 2711 2775 135 2429 2546 183 4717 4756 160 2546 2627 148 3844 3925 8 4529 4531 38 677 689 133 3216 3220 43 2035 2148 175 4827 4941 8 3177 3180 140 3119 3180 57 1419 1493 79 2198 2264 150 3125 3148 22 2997 3078 22 3117 3177 195 894 1019 12 4760 4815 135 1493 1625 77 89 172 188 3919 4026 28 4494 4575 28 1956 2065 31 1625 1746 187 570 624 57 3245 3356 136 2932 2970 148 3013 3019 195 3085 3125 5 2853 2932 104 412 556 200 1419 1426 22 1557 1675 7 2627 2732 104 1182 1244 28 1625 1628 189 2286 2291 188 3630 3725 58 2381 2529 28 1910 2035 133 3239 3372 58 4092 4097 54 7 53 120 4120 4197 31 4197 4302 79 4749 4819 120 394 399 113 3844 3911 150 3400 3630 77 2641 2708 57 2623 2641 28 4756 4757 187 2375 2429 197 1746 1811 55 964 1019 197 2305 2366 135 2761 2787 121 3113 3114 127 3013 3019
Output
185
Almost adjacent Test
Input
2 50 9 10 80 11 12
Output
7
Validator 11 Validator
Input
2 20 50 51 10 52 53
Output
7
Solution language
Solution
Stub generator input
ABOUT USCAREERSPRIVACYFAQBLOG
ABOUT USCAREERSPRIVACYFAQBLOG

The #1 tech hiring platform

SCREENINGINTERVIEWING
FacebookYouTubeTwitterLinkedIn