mehrshadlotfi's blog

Algorithm for connecting 2 array of points
By mehrshadlotfi, history, 8 years ago, In English

We have n black points and n white points with their x values. If we connect each black point with a white point by wire. Which algorithm will cause the lowest wire needed.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What about kruskal?

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What are values? It sounds like the Hungarian algorithm.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    integers I think i found the answer, with greedy algorithm, o(nlogn).

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Suppose we have a sorted list of the white point positions and the black point positions. Then we should match the i-th white dot with the i-th black dot.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I meant: what do "values" represent?

        I guess your algorithm isn't correct but first, please explain what values are.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ok, so points are on the line? Not on the plane? Then yep, greedy works.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            But the greedy doesn't make a true solution in sample input : (0,2) (1,4) (3,5) dist = 7

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              A better solution could be: (1,2) (3,4) (1,5) dist = 6

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Once you used 0,1,3 as the first set and once you used 1,1,3.

                → Reply