The profile

In my last blog post, LeetCode Advanced 944- Greedy, a friend suggested that 944 is not very representative of understanding greedy algorithms. After reviewing the content of the next chapter, the blogger focuses on the small skills of algorithm optimization in the actual article, and the idea of solving the problem is just a simple statistical method, which does not really help greedy thoughts. Based on this, the blogger has corrected the title of the last blog to “LeetCode Advanced 944- Algorithm Optimization” (except the subscription number due to the limitation of wechat public platform, the title cannot be modified temporarily), and this article will take LeetCode 1029 as an example to explain the idea of greedy algorithm.

Small talk

Unconsciously, blog from start algorithm and a half months have passed by now, in the process also encountered many difficulties, actually also once wanted to give up, deeply realize there is no one thing can be simple to elaborate the past, especially can understand those can work ten years like one day insist technology the authors of the article writing is not easy. However, despite the hard work, I have gained a lot, such as striving for perfection and pursuing more perfection. For example, I have gained a lot of knowledge beyond technology, made more friends and broadened my vision. I still remember the first successful submission, the first time the article was included in a big column, the first time someone praised, the first time fans paid attention to, and even the first time a platform fans broke 100 when the inner joy… In the future, I hope I can write algorithm blog as a hobby all the time, and also hope that these articles can bring practical help to friends in need. In the process of pushing the following blog posts, there will be some omissions or misunderstandings in thinking and understanding, welcome to exchange or criticism.

The original problem

1029. Two City Scheduling

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

Example 1:

Input: [[10,20],[30,200],[400,50],[30,20]] Output: 110 Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20.

The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Note:

1 <= costs.length <= 100 It is guaranteed that costs.length is even. 1 <= costs[i][0], costs[i][1] <= 1000

1029. Interview Arrangement (named according to the assignment)

The company arranged for 2N people to attend the interview. The cost for the ith person to fly to city A by plane is Costs [I][0], and costs[I][1] to fly to city B.

Return the minimum cost of arranging for each person to go to A city for an interview, N people in each city A and B.

Ex. :

Input: [[10,20],[30,200],[400,50],[30,20]] output: 110 description: for the first person to go to city A, the fee is 10. The second person goes to City A for 30. The third person goes to city B for $50. The fourth person will go to city B for $20.

The minimum total cost is 10 + 30 + 50 + 20 = 110, and half of the people in each city are interviewing.

Tip:

1 <= costs[I][0], costs[I][1] <= 1000 costs

  • This problem falls under the category of greedy algorithms in LeetCode

Analysis of the question

2N people need to be divided into two groups and sent to city A and city B respectively for interview. The cost of each person going to city A and city B is known, so the total cost should be minimum. All things involving the maximum minimum sum related topic, nature is not hard to think of greedy algorithm, greedy thought “knapsack problem”, is the most typical problems about greedy thought is important to note that it is important to ensure that the “greedy” approach is correct or can get the optimal solution, in the process of practice can be numerical into concrete.

Concept design

The optimal solution is to arrange N people to go to A and B for interviews at the least cost. There is A price difference between the cost of each person to go to A and B. Can understand this simple so we can be unified calculate everyone to B city to A city need to spend more money than the (also can be in A city than to B cities need to spend much money), and then sorted, biggest ranked first price differential of can only arrange to A city, it can save the cost of the largest. The second person in line can only be arranged to city A until the person in line N is arranged to city A, and the remaining N people are all arranged to city B because it costs less to go to city B than to go to city A.

Pseudo code:

1, create an int array sort of the same size as the number of people, which saves the cost of each person traveling to city B than to city A. 2. Traverse the costs array and record the difference in the sort array element; I. Calculate the difference between person I's trip to B and trip to A; Ii. The difference shifted 8 bits to the left; Iii. Left shift followed by the current subscript position I in the cost array; 3, Sort the difference array; 4, declare an int variable min to represent the sum of the minimum costs, loop through sort array, the number of times only needs to be half of the number of costs. Length /2; I. For the top N in the difference value, that is, the last N person in sort, select the cost of going to City A and obtain the cost from the Costs array according to the subscript position in the Costs array stored by the SORT element; Ii. For N individuals ranked after the difference value, that is, the top N individuals in sort, select the cost of going to city B, and obtain the cost from the Costs array according to the subscript position in the Costs array stored by the SORT element; Iii.min Adds up all total costs;Copy the code

Coding practices

	public int twoCitySchedCost(int[][] costs) {
		int sort[] = new int[costs.length];
		for (int i = 0; i < costs.length; ++i) {
			sort[i] = ((costs[i][1] - costs[i][0]) << 8) + i;
		}
		Arrays.sort(sort);
		int min = 0;
		for (int i = 0; i < sort.length / 2; ++i) {
			int index1 = sort[costs.length - 1 - i]  & 0xFF;
			int index2 = sort[i]  & 0xFF;
			min = min + costs[index1][0] + costs[index2][1];
		}
		return min;
	}
Copy the code

eggs

If you look at the implementation code above, you can see that when storing the int price difference to cities B and A in the sort array and the subscript position in the Costs array, you use the operation of moving 8 bits left and then adding I. This is the Easter egg of this article, and all the Easter eggs will be explained in the following tweets.

conclusion

This paper with 1029 examples demonstrate understanding of greedy thought, thought is relatively simple easy to understand, and can be seen from the submitted results practices code efficiency of the greedy algorithm thought has defeated the 99% of the algorithm, so the exhaustive method is another method to do detailed instructions, readers can consider their using exhaustive method for implementation. For the leetcode Progression blog series, there will be a more systematic progression outline, please look forward to it