1
+ <?php
2
+ // You need to install Data Structures (DS) extension.
3
+ // More details here - http://php.net/manual/en/book.ds.php
4
+ use \Ds \Set ;
5
+
6
+ $ statesNeeded = new Set (["mt " , "wa " , "or " , "id " , "nv " , "ut " , "ca " , "az " ]);
7
+ $ stations = [];
8
+ $ stations ["kone " ] = new Set (["id " , "nv " , "ut " ]);
9
+ $ stations ["ktwo " ] = new Set (["wa " , "id " , "mt " ]);
10
+ $ stations ["kthree " ] = new Set (["or " , "nv " , "ca " ]);
11
+ $ stations ["kfour " ] = new Set (["nv " , "ut " ]);
12
+ $ stations ["kfive " ] = new Set (["ca " , "az " ]);
13
+ $ finalStations = new Set ();
14
+
15
+ while (!$ statesNeeded ->isEmpty ()) {
16
+ $ bestStation = null ;
17
+ $ statesCovered = new Set ();
18
+ foreach (array_keys ($ stations ) as $ station ) {
19
+ $ states = $ stations [$ station ];
20
+ $ covered = new Set ($ statesNeeded );
21
+ $ covered = $ covered ->filter (function ($ value ) use ($ states ) {
22
+ return $ states ->contains ($ value );
23
+ });
24
+ if ($ covered ->count () > $ statesCovered ->count ()) {
25
+ $ bestStation = $ station ;
26
+ $ statesCovered = $ covered ;
27
+ }
28
+ }
29
+ $ statesNeeded = new Set ($ statesNeeded );
30
+ $ statesNeeded = $ statesNeeded ->filter (function ($ value ) use ($ statesCovered ) {
31
+ return !$ statesCovered ->contains ($ value );
32
+ });
33
+ $ finalStations ->add ($ bestStation );
34
+ }
35
+
36
+ print_r ($ finalStations ); // ["kone", "ktwo", "kthree", "kfive"]
0 commit comments