算法题之装空调

前言

昨天看到一个算法题，挺有意思的，大家分享下，这道题被定义为困难。

题目

学校要装空调了！！！

9102年，学校终于要装空调了，学生们都欢呼雀跃的期待着学校赶紧把空调装好。但是学校招过来的安装空调的人却不够了，同一时间只能安装一个空调，这引起了大家的不满。大家都希望学校能够先装自己宿舍，如果装的太晚就要抗议。

假设学校共有 n 栋宿舍楼，每栋宿舍楼有 m 间宿舍，每间宿舍都有大小不同的忍受度。学校装空调时，只能把同一栋楼的空调安装完毕后才能安装其他宿舍楼的空调。

作为校长精明能干的助手，校长希望你能够安排好学校安装空调的顺序，让抗议的宿舍数最少。（增添人手的钱都用来买空调了，别想在招人了）

入参有三个，第一个输入一个整数n，表示n栋宿舍楼；
第二个输入一个整数m，表示每栋楼有m间宿舍；
接下来输入一个n*m的矩阵，表示每栋宿舍楼的每间宿舍的忍受度f(ij)。
(1 <= n <=20 ,1<=m <=1000,1<=f(ij)<=n *m)。

注释：忍受度：如果某个宿舍宿舍是所有宿舍（包含其他宿舍楼的宿舍）中第 x 个装空调的(x > f_{ij}) , 那么这个宿舍就要去抗议。
输出最少的抗议的宿舍数。

示例1

输入：
3
3
[[3,1,2],[6,5,8],[7,3,4]]
输出：
2

注意
安装空调的顺序依次为：


(1,2)，(1,3)，(1,1)
(2,2)，(2,1)，(2,3)
(3,1)，(3,2)，(3,3)

实现代码

package solution70;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution {
    private int minCount = Integer.MAX_VALUE;
    private int position = 0;//from 1
    private int currentCount = 0;
    private List<Floor> floors;
    private int n;
    private int m;
    private List<Room> orderedRooms = new ArrayList<>();

    public int solution(int n, int m, int[][] f) {
        initData(n, m, f);
        this.start();
        return minCount;
    }

    private void initData(int n, int m, int[][] f) {
        this.n = n;
        this.m = m;
        int i = 0;
        int j;
        ArrayList<Floor> floors = new ArrayList<>();
        for (; i < n; i++) {
            ArrayList<Room> rooms = new ArrayList<>();
            for (j = 0; j < m; j++) {
                rooms.add(new Room(false, f[i][j], i + 1, j + 1));
            }
            sortRooms(rooms);
            Floor floor = new Floor(false, rooms);
            floors.add(floor);
        }
        this.floors = floors;
    }

    private void sortRooms(List<Room> rooms) {
        rooms.sort(new Comparator<Room>() {
            @Override
            public int compare(Room o1, Room o2) {
                return o1.getEndurance() - o2.getEndurance();
            }
        });
    }

    private void start() {
        boolean allChecked = true;
        FloorResult result;
        for (Floor f :
                floors) {
            if (!f.isChecked()) {
                f.setChecked(true);
                result = calculateFloor(f);
                allChecked = false;
                position -= result.getIterateCount();
                currentCount -= result.getCount();
                f.setChecked(false);
            }
        }
        //the last floor
        if (allChecked) {
            if (currentCount < minCount) {
                minCount = currentCount;
                printRoom();
            }
            System.out.println("min:" + minCount + " and now:" + currentCount);
        }
    }

    private void printRoom() {
        for (Floor f :
                this.floors) {
            System.out.println("-----------------");
            for (Room m :
                    f.getRooms()) {
                System.out.println("(" + m.getPosition() + "," + m.getEndurance() + ")");
            }
            System.out.println("-----------------");
        }
    }

    private FloorResult calculateFloor(Floor floor) {
        boolean afterShouldProtest = false;
        FloorResult result = new FloorResult();
        int reservedPosition;
        int reservedCount;
        boolean isFound = false;
        // List<Room> cur = new ArrayList<>();
        for (Room r :
                floor.getRooms()) {
            if (!r.isChecked()) {
                result.incrIterateCount();
                position++;
                r.setChecked(true);
                isFound = false;
                //cur.add(r);
                if (r.getEndurance() < position) {
                    for (Room m :
                            floor.getRooms()) {
                       /* boolean checked = m.isChecked();
                        m.setChecked(true);*/
                        if (!m.isChecked() && m.getEndurance() >= position) {
                            //skip
                            m.setChecked(true);
                            isFound = true;
                            m.setPosition(position);
                            break;
                        }
                    }
                    r.setPosition(0);
                    currentCount++;
                    result.incrCount();
                    if (!afterShouldProtest) {
                        afterShouldProtest = true;
                    }
                    if (currentCount >= minCount) {
                        //restore
                        for (Room k :
                                floor.getRooms()) {
                            k.setChecked(false);
                        }
                        return result;
                    }
                } else {
                    r.setPosition(position);
                }
            }
        }
        //restore
        for (Room r :
                floor.getRooms()) {
            r.setChecked(false);
        }
        reservedPosition = position;//reserve
        reservedCount = currentCount;
        //next floor
        start();
        position = reservedPosition;
        currentCount = reservedCount;
        return result;
    }

    private static class Floor {
        private boolean isChecked;
        private List<Room> rooms;

        public Floor(boolean isChecked, List<Room> rooms) {
            this.isChecked = isChecked;
            this.rooms = rooms;
        }

        public boolean isChecked() {
            return isChecked;
        }

        public void setChecked(boolean checked) {
            isChecked = checked;
        }

        public List<Room> getRooms() {
            return rooms;
        }

        public void setRooms(List<Room> rooms) {
            this.rooms = rooms;
        }

        public void addRoom(Room room) {
            rooms.add(room);
        }
    }

    private static class Room {
        private boolean isChecked;
        private int endurance;
        private int x;
        private int y;
        private int position;

        public Room(boolean isChecked, int endurance, int x, int y) {
            this.isChecked = isChecked;
            this.endurance = endurance;
            this.x = x;
            this.y = y;
        }

        public boolean isChecked() {
            return isChecked;
        }

        public void setChecked(boolean checked) {
            isChecked = checked;
        }

        public int getEndurance() {
            return endurance;
        }

        public void setEndurance(int endurance) {
            this.endurance = endurance;
        }

        @Override
        public String toString() {
            return "Room{" +
                    "isChecked=" + isChecked +
                    ", endurance=" + endurance +
                    ", x=" + x +
                    ", y=" + y +
                    '}';
        }

        public int getPosition() {
            return position;
        }

        public void setPosition(int position) {
            this.position = position;
        }
    }

    private static class FloorResult {
        private int iterateCount;
        private int count;

        public FloorResult() {
        }

        public FloorResult(int iterateCount, int count) {
            this.iterateCount = iterateCount;
            this.count = count;
        }

        public int getIterateCount() {
            return iterateCount;
        }

        public void setIterateCount(int iterateCount) {
            this.iterateCount = iterateCount;
        }

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
        }

        public void incrIterateCount() {
            iterateCount++;
        }

        public void incrCount() {
            count++;
        }
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接