[PYTHON] Algorithm power UP! Let's solve "ABC 103 D --Island War"

What you can see by reading the article

--Understanding the solution of the article author's "ABC 103 D --Island War" --Understanding the author's approach to the algorithm problem

This issue

** ABC 103 D --Island War ** → Click here for problem statement

Article author's answer code

from operator import itemgetter

# ==============================================================
  # return:Output how many bridges should be removed when a request is given to prevent N islands and M islands from going back and forth.
  # pre:  5 2   
        # 1 4
        # 2 5
  # post:　1 ->1 if only the bridge between 2 and 4 is removed,4 2,You will not be able to go back and forth between 5.
  # ==============================================================

  #★ step1 Question sentence N,Make M an int type and make it a variable
  #★ step2 Given a,Sort the requests of b in ascending order of b
  #                      ->Implementation:Remove the bridge between the given requests a b and make it inaccessible.
  #                         idx a b
  #                      -> 0:  1 3                  　1 2
  #                         1:2 4 if 2,Exclude between 3 2 If 3 1,2 2,Exclude between 3
  #                      ->Exclude one bridge if the next a is smaller than the previous b,Exclude two bridges if it is greater than or equal to the value of a next to the previous b
  #                      ->Sort b in ascending order so that you can see the value of the previous b by the value of the next a to see if you want to remove the bridge.
  #★ step3 Determine if the next value of a is greater than or equal to the previous value of b
  #★ step4 If the value of the next a is greater than or equal to the value of the previous b, increment the number to be removed and update the value of the previous b with the current value of b.


#Get N and M
N, M = map(int, input().split())

#Index a for M islands,Get the requests that b does not come and go as an array
ab_requests =  [tuple(map(int, input().split())) for _ in range(M)]

#Sort in ascending order of b value
#Looking at the document, the key=itemgetter(num)Looks good-> https://docs.python.org/3/howto/sorting.html
ab_requests_sorted = sorted(ab_requests,key=itemgetter(1))


prev_b = -1
next_a = -1
removed_counts = 0

for a, b in ab_requests_sorted :
  #Use as the next a
  next_a = a
  #Determine if the next value of a is greater than or equal to the previous value of b
  #Larger case[(1,2),(3,4)]And the above cases[(1,2),(2,3)]Note
  if prev_b <= next_a :
    #Increment the number of bridges to remove
    removed_count += 1
    #Update the previous b so that you can compare the value with the next a
    prev_b = b 

#Output result
print(removed_count)

Explanation of the answer

Answer points of this algorithm problem that the author of the article thinks

――Try to enter a specific number so that you can actually imagine it, and verify in what cases the number to be removed will increase. (In this case, the number to be removed changes by comparing the value of the previous b with the value of the next b.)